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

Can Olcott agree on these 8 points?

9 views
Skip to first unread message

immibis

unread,
Jan 21, 2024, 10:17:46 AMJan 21
to


1. A Turing machine is defined as 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. A tape for a Turing machine is defined as a finite list of symbols
from that machine's alphabet, exactly one of which is labeled as the
current position.

3. An execution point (this is a term I made up) for a Turing machine is
defined as a state number from that machine's state list and a tape for
that machine.

4. Stepping (this is a term I made up) an execution point (P1)
calculates a new execution point (P2) according to the machine's
transition table according to the following rules:

4a. The active transition (AT) is the one which is found by looking up
(P1.state, P1.tape.symbols[P1.tape.position]) in the machine's
transition table.
4b. P2.state = AT.state
4c. P2.tape.symbols = P1.tape.symbols except for
P2.tape.symbols[P1.tape.position] = AT.symbol
4d. If AT.direction=left then P2.tape.position = P1.tape.position-1
4e. If AT.direction=right then P2.tape.position = P1.tape.position+1

5. The execution sequence (this is a term I made up) of a machine M and
initial execution point P0 is the sequence [P0, P1, P2, P3, ...]
where
P1 = stepping(M,P0)
P2 = stepping(M,P1)
P3 = stepping(M,P2)
...etc...
The execution sequence ends at the first Pn whose state is an
accepting state for M.
It's possible for an execution sequence to have infinite length.

6. An execution sequence of a Turing machine contains a finite number of
execution points or an infinite number of execution points.

7. Turing machines, execution points, tapes, and execution sequences are
pass-by-value.
This is because everything in maths is pass-by-value, even though
Olcott might not understand this.

8. Reasoning about Turing machines on the basis of any machine that is
not isomorphic to Turing machines is invalid.



immibis

unread,
Jan 21, 2024, 7:04:18 PMJan 21
to
It seems that Olcott cannot agree on these 8 points.
0 new messages