Add multi-tape Turing machine
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
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:
- Allow users to add input on multiple tapes.
- 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
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from EvalVis/TuringMachine
-
enhancement good first issue
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
EvalVis/TuringMachine#1 ·
-
Add tests Openenhancement good first issue
Difficulty 4/5 3-5 days Newbie friendliness 35/100
EvalVis/TuringMachine#6 ·
-
enhancement good first issue
Difficulty 5/5 Over a week Newbie friendliness 35/100
EvalVis/TuringMachine#5 ·
-
enhancement good first issue
Difficulty 3/5 1-2 days Newbie friendliness 45/100
EvalVis/TuringMachine#4 ·
-
User login Openenhancement good first issue
Difficulty 5/5 Over a week Newbie friendliness 25/100
EvalVis/TuringMachine#3 ·
All issues in EvalVis/TuringMachine
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
Eynzof/Hermes-CN-Desktop#610 ·
-
bug clawsweeper:linked-pr-open clawsweeper:needs-live-repro clawsweeper:no-new-fix-pr impact:message-loss issue-rating: 🐚 platinum hermit P2 regression
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
-
enhancement
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
calcite-components needs triage refactor
Difficulty 2/5 1-3 hours Newbie friendliness 75/100
Esri/calcite-design-system#15203 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 90/100
danielmiessler/LifeOS#2218 ·