Skip to content

Instantly share code, notes, and snippets.

@CodaFi
Forked from garrigue/turing.ml
Last active November 25, 2021 00:50
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save CodaFi/45347417cad448c6ec4ab4494237a47e to your computer and use it in GitHub Desktop.
Save CodaFi/45347417cad448c6ec4ab4494237a47e to your computer and use it in GitHub Desktop.
struct State0 {}; struct State1 {}; struct FinalState {} /*States*/
struct Symbol {}; struct Blank {} /*Symbols*/
struct Left {}; struct Right {} /*Directions*/
struct EndOfTape {} /*End of Tape*/
struct Transition<StartState, StartHead, EndState, EndHead, Direction> {
static func transitionOne() -> Transition<State0, Blank, State1, Symbol, Left> { fatalError() }
static func transitionTwo() -> Transition<State1, Blank, State0, Symbol, Right> { fatalError() }
static func transitionThree<State>() -> Transition<State, Symbol, FinalState, Symbol, Left> { fatalError() }
}
struct Evaluate<State, Head, Left, Right> {
static func final() -> Evaluate<FinalState, Head, Left, Right> { fatalError() }
static func moveLeft<StartState, StartHead, EndState, EndHead>(
_ : Transition<StartState, StartHead, EndState, EndHead, Left>,
_ : Evaluate<EndState, EndHead, Left, (EndHead, Right)>
) -> Evaluate<StartState, StartHead, (Head, Left), Right> { fatalError() }
static func moveRight<StartState, StartHead, EndState, EndHead>(
_ : Transition<StartState, StartHead, EndState, EndHead, Right>,
_ : Evaluate<EndState, EndHead, (EndHead, Left), Right>
) -> Evaluate<StartState, StartHead, Left, (Head, Right)> { fatalError() }
static func extendLeft<State, Head>(
_ : Evaluate<State, Head, (Blank, EndOfTape), Right>
) -> Evaluate<State, Head, EndOfTape, Right> { fatalError() }
static func extendRight<State, Head>(
_ : Evaluate<State, Head, Left, (Blank, EndOfTape)>
) -> Evaluate<State, Head, Left, EndOfTape> { fatalError() }
}
typealias Goal = Evaluate<State0, Blank, EndOfTape, EndOfTape>
func doesItHalt(_ goal : Optional<Goal>) -> Void {
// switch goal {
// case .none:
// break
// // Am I exhaustive?
// }
}
struct State0 {}; struct State1 {}; struct FinalState {} /*States*/
struct Symbol {}; struct Blank {} /*Symbols*/
struct Left {}; struct Right {} /*Directions*/
struct EndOfTape {} /*End of Tape*/
enum Transition<StartState, StartHead, EndState, EndHead, Direction> {
case transitionOne : Transition<State0, Blank, State1, Symbol, Left>
case transitionTwo : Transition<State1, Blank, State0, Symbol, Right>
case transitionThree<State> : Transition<State, Symbol, FinalState, Symbol, Left>
}
enum Evaluate<State, Head, Left, Right> {
case final : Evaluate<FinalState, Head, Left, Right>
case moveLeft<StartState, StartHead, EndState, EndHead>(
_ : Transition<StartState, StartHead, EndState, EndHead, Left>,
_ : Evaluate<EndState, EndHead, Left, (EndHead, Right)>
) : Evaluate<StartState, StartHead, (Head, Left), Right>
case moveRight<StartState, StartHead, EndState, EndHead>(
_ : Transition<StartState, StartHead, EndState, EndHead, Right>,
_ : Evaluate<EndState, EndHead, (EndHead, Left), Right>
) : Evaluate<StartState, StartHead, Left, (Head, Right)>
case extendLeft<State, Head>(
_ : Evaluate<State, Head, (Blank, EndOfTape), Right>
) : Evaluate<State, Head, EndOfTape, Right>
case extendRight<State, Head>(
_ : Evaluate<State, Head, Left, (Blank, EndOfTape)>
) : Evaluate<State, Head, Left, EndOfTape>
}
typealias Goal = Evaluate<State0, Blank, EndOfTape, EndOfTape>
func doesItHalt(_ goal : Optional<Goal>) -> Void {
switch goal {
case .none:
break
// Am I exhaustive?
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment