EvalVis / EvalVis/TuringMachine
Add multi-tape Turing machine
- Dominant language
- TypeScript
- Stars
- 0
- Forks
- 0
- PR merge metrics
- No merged PRs in 30d
Description
**Describe the feature**
Add multi-tape Turing machine so more difficult problems are easier to solve. Example: addition of two numbers is quote complex taking lots of transition table space in classical Turing machine.
Multi-tape Turing machine has multiple tapes and multiple heads writing and moving independently on each tape.
The machine has a single state.
Task: create a new machine from classical Turing machine which in addition to Turing machine functionality:
1. Allow users to add input on multiple tapes.
2. Allows user to input transition table of rows: current state, tape 1 current symbol, tape 2 current symbol..., -> next state, write symbol tape 1, write symbol tape 2..., move direction tape 1, move direction tape 2...
So, for each state, depending on every symbol tapes encounter you declare a new state, order each of the heads to write a specific symbol independently and move independently.
**Describe alternatives you've considered (optional)**
Although every problem which can be solved with multi-tape Turing machine can also be solved with classical Turing machine, having a multi-tape Turing machine makes coding and visualizing easier.
**Additional context**
Example:
Blank symbol is `_`.
Starting state is `q0`.
Final state is `HALT`.
Input is on tape 1 and tape 2.
Output is on tape 3.
Transition table:
```csv
q0,0,0,_,->q0,0,0,_,R,R,S
q0,1,0,_,->q0,1,0,_,R,R,S
q0,0,1,_,->q0,0,1,_,R,R,S
q0,1,1,_,->q0,1,1,_,R,R,S
q0,_,_,_,->q1,_,_,_,L,L,L
q1,0,0,_,->q1,0,0,0,L,L,L
q1,0,1,_,->q1,0,1,1,L,L,L
q1,1,0,_,->q1,1,0,1,L,L,L
q1,1,1,_,->q2,1,1,0,L,L,L
q1,0,_,_,->q1,0,_,0,L,L,L
q1,_,0,_,->q1,_,0,0,L,L,L
q1,1,_,_,->q1,1,_,1,L,L,L
q1,_,1,_,->q1,_,1,1,L,L,L
q1,_,_,_,->HALT,_,_,_,S,S,S
q2,0,0,_,->q1,0,0,1,L,L,L
q2,0,1,_,->q2,0,1,0,L,L,L
q2,1,0,_,->q2,1,0,0,L,L,L
q2,1,1,_,->q2,1,1,1,L,L,L
q2,0,_,_,->q1,0,_,1,L,L,L
q2,_,0,_,->q1,_,0,1,L,L,L
q2,1,_,_,->q2,1,_,0,L,L,L
q2,_,1,_,->q2,_,1,0,L,L,L
q2,_,_,_,->q1,_,_,1,S,S,S
```
You can test it with input:
```
Tape 1:111
Tape 2: 111
Tape 3: totally blank
```
Result should be:
```
Tape 1:111
Tape 2: 111
Tape 3: 1110
```
Note: although output might still be verbose its much easier to think of the solution in multi-tape Turing machine instead of classical Turing machine.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.