A simple Turing machine interpreter
git clone https://github.com/SpanishInquisition49/TuringMachine.git
- if you don't have TypeScript
npm install -g typescript
tsc turing.ts
node ./turing.js
The interpreter take 3 parameters:
//an array containing all the possible states the machine can take.
states: State[]
// an array of characters representing the initial content of the tape.
tape: string[]
//an integer representing the execution speed in milliseconds.
speed: number
The machine always start with state 0
and the pointer on position 0
.
The machine stop when it can't change state and it print the content of the tape and the pointer position.
A state is a 5-tuple of the form (CS, TR, NS, TW, PM)
:
-
CS
or current state is the state that the machine has to have before do the transition. -
TR
or tape read is the content of the tape that the machine has to have in order to do the transition. -
NS
or new state is the state that the machine take after the transition. -
TW
or tape write is the content that will be wrote on the tape durning the transition. -
PM
or pointer movement is a token representing the direction of the movement which the pointer make during the transition.Token Direction <
Left >
Right _
Stay
(0, A, 1, B, >)
is equal to: if you are in the state 0
and you are reading A
then go in the state 1
, write B
and move the pointer to the right.
This table contain all the special character usable in the TR
and TW
Token | Name | Description | Readable | Writable |
---|---|---|---|---|
** |
AnyNotEmpty | Any character except Empty | ✅ | ❌ |
_ |
Empty | Empty character | ✅ | ✅ |
__ |
Space | Space character | ✅ | ✅ |
# |
Comment | if it's the first character in the entire line then the line will be ignored. | ✅ | ✅ |
[-] |
Pattern | A shorthand for multiple states | ✅ | ✅ / ❌1 |
1: Writable only if there is a pattern in TR
Patterns are shorthands to multiple state writing.
Insted of:
(0, A, 1, B, >)
(0, B, 1, C, >)
(0, C, 1, D, >)
You can write:
(0, [A-C], 1, [B-D], >)
Insted of:
(0, A, 1, B, >)
(0, B, 1, B, >)
you can write:
(0, [A-B], 1, B, >)