immibis
unread,Jan 21, 2024, 12:29:17 PMJan 21You do not have permission to delete messages in this group
Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message
to
1. A Turing machine is a finite list of alphabet symbols, a default
symbol, a list of state numbers, an initial state number, a finite list
of accepting state numbers, and a transition table which maps each
(state × symbol) to another (state × symbol × direction).
2. Any Turing machine T and initial tape (defined as a sequence
2. The initial line of the execution trace trace(0) contains the initial
state number, and a tape consisting of one copy of the default symbol,
which is marked as the current position.
3. Each subsequent line of the execution trace trace(n+1) is formed
according to trace(n) by the following rules (applied simultaneously):
a. The active transition is the one which (trace(n) state number,
trace(n) tape symbol at trace(n) current position) maps to in the
transition table
b. trace(n+1) state number is the active transition's state
c. trace(n+1) symbol at trace(n) current position is the active
transition's symbol
d. trace(n+1) current position is trace(n) current position, moved
one cell left or right according to the active transition's direction
e. If the current position moves off the end of the tape, a default
symbol is added underneath the new current position.
4. The execution trace of a Turing machine is the sequence of steps
formed by repeatedly applying the rules in step 3 until it generates a
line with an accepting state number.
5. The execution trace of a Turing machine contains a finite number of
lines or an infinite number of lines.
6. If I tell you a Turing machine, can you figure out whether its
execution trace has a finite number of lines or an infinite number of lines?