Lab Introduction
- It is strongly recommended to use the chrome browser to avoid possible display problems.
- In this lab, you need to independently complete three Turing machine state transition tables that each
solves the following three problems.
Lab Content
Turing machine simulator description
- The input is put on the tape, and other square are letter B.
- Header is initially on the far-left side of the input string
Buttons Description
- "Set": Initialize Turing machine, including import rules and tape data
initialization.
- "Pause”/“Continue": Pause or continue execution.
- "Debug": Invalid when in continue state, otherwise execute one step.
- "{{">>"}}": Speed up the execution.
- "{{"<<"}}" : Slow down the execution
- "Finish": Skip animation and display the result of the Turing machine.
- "Test": See if you can pass a test point.
- "Submit": upload student current state-transition table.
- "Recover": download student last submitted state-transition table.
Caution: If the number of moving steps exceeds 10,000 steps, it will be regarded as
non-stop.
Turing machine simulator 6-tuple description
Only a state-transition table is needed as input of Turing machine simulator.
The state transition table consists of several rows, each row contains a transition rule,
which has
five parts: State, Symbol Read, Symbol to Write, Head Move and Next State in sequence,
separated by commas ",".
Note:
- State / Next State: a string. Specify q0 as the starting state and qa as the stop state.
- Symbol Read: a visible ASCII character, represent the letter that head read.
- Symbol Read: a visible ASCII character, represent the letter that head read.
- Head Move: One of {{"{"}}L, R{{"}"}}, where L means the head moves one space to the left, R means the
head moves one space to the right.
- Case sensitive.
For the remaining part of the six-tuple, we obtain it in the following way:
- State Set: Q is generated according to the state transition table,
including all the states that have appeared in the "state"/"next state" column of the state transition
table.
- Tape Symbols Set: Γ is specified as all the visible ASCII codes.
- Input Symbol Set: Σ is a subset Γ\{{"{"}}B{{"}"}}.
- initial state: q0.
- stop state: qa.
The following is an example:
q0, B, B, R, q1
q1, B, 1, L, qa
Its function is: if the current position is empty, move head
one step to the right.
if it is still empty, write 1, move one step to the left, and then stop.
Turing machine input description:
- The input should be a string consisting of letters in the input symbol set.
Three Questions
- Question 1:Unary addition
Input:(some 1)+(some 1)=
Output on tape:…###(some 0 or 1)B###...
- TThe input "a number of 1s" represents the unary number to be added, which may be zero ones; the "a number of 1s" on the paper tape when the machine stops.
-
The starting position of result should be one square to the right of the original position of = in the input, and end with B; # is any letter in Γ.
Samples:
- Input: 11+1=
- Output on tape: ...11+1=111B...
- Input: 11+1=
- Output on tape: ...FBc01111BcWW...
- Question 2: Binary addition of two 4-bit numbers
Input: (4-bit 0 or 1)+(4-bit 0 or 1)=
Output on tape: ...###(5-bit 0 or 1)B###...
-
The input “4-bit 0 or 1” represents the binary number to be added; the “5-bit 0 or 1” on the tape when the machine stops (pay attention to the leading 0 when the result is only 4 digits).
-
The starting position of result should be one square to the right of the original position of = in the input, and end with B; # is any letter in Γ.
Samples:
- Input: 1101+0011=
- Output on tape: ...1101+0011=10000B...
- Input: 0001+0011=
- Output on tape: ...001101101000100B000...
- Question 3: Binary addition of two arbitrary numbers
Output on tape: (some 0 or 1)+(some 0 or 1)=
Output on tape: ...###(some 0 or 1)B###...
- The input “some 0 or 1" must not contain leading 0s; the length of each operand is greater than or equal to 1. The “some 0 or 1” on the tape when the machine stops.
-
The result should not contain leading 0s. The starting position of result should be one square to the right of the original position of = in the input, and end with B; # is any letter in Γ.
Samples:
- Input:1+1001=
- Output on tape: ...11+1001=1100B...
- Input:11+1001=
- Output on tape: ...wRQTqLaA1100BssR...
Submition
- Click Submit button in the corresponding experiment, and the assignment submission of the experiment
will be completed after success.