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?

This was sent accidentally and should be ignored. I haven't learned how
to cancel it yet.

On 1/21/24 15:29, immibis wrote:
> 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?
>