Add multi-tape Turing machine

Open
#7 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
5/5
Estimated time
Over a week
Newbie friendliness
30/100
Issue type
Feature
Clarity
Mostly clear
Activity status
Stale
Tech stack
typescript
Domain
tooling

Research direction

No files or tests are named. Start by inspecting the existing classical Turing machine implementation, especially its input and transition-table handling. Done means users can configure multiple tapes and independently read, write, and move each head, with the supplied addition example producing 1110 on tape 3.

Written by the indexing model from the issue text.

Description

enhancement

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:

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.

Dominant language
TypeScript
Stars
0
Forks
0
PR merge metrics
No merged PRs in 30d

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from EvalVis/TuringMachine

All issues in EvalVis/TuringMachine

Similar issues

More TypeScript issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.