EvalVis / EvalVis/TuringMachine

Add multi-tape Turing machine

Open
#7 0 comments 0 reactions 0 assignees View on GitHub
enhancement
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.