Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Does Olcott accept these definitions? (Turing machine; execution trace)

5 views
Skip to first unread message

immibis

unread,
Jan 21, 2024, 12:29:17 PMJan 21
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?

immibis

unread,
Jan 21, 2024, 12:53:22 PMJan 21
to
This was sent accidentally and should be ignored. I haven't learned how
to cancel it yet.
0 new messages