What's your definition of a Turing machine? I think we're talking at
cross purposes. I posted the definition from Wikipedia:
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
A Turing machine is a mathematical model of computation describing an
abstract machine[1] that manipulates symbols on a strip of tape
according to a table of rules.[2] *Despite the model's simplicity, it is
capable of implementing any computer algorithm.[3]
*
The machine operates on an infinite[4] memory tape divided into discrete
cells,[5] each of which can hold a single symbol drawn from a finite set
of symbols called the alphabet of the machine. It has a "head" that, at
any point in the machine's operation, is positioned over one of these
cells, and a "state" selected from a finite set of states. At each step
of its operation, the head reads the symbol in its cell. Then, based on
the symbol and the machine's own present state, the machine writes a
symbol into the same cell, and moves the head one step to the left or
the right,[6] or halts the computation. The choice of which replacement
symbol to write, which direction to move the head, and whether to halt
is based on a finite table that specifies what to do for each
combination of the current state and the symbol that is read. Like a
real computer program, it is possible for a Turing machine to go into an
infinite loop which will never halt.
The Turing machine was invented in 1936 by Alan Turing,[7][8] who called
it an "a-machine" (automatic machine).[9] It was Turing's doctoral
advisor, Alonzo Church, who later coined the term "Turing machine" in a
review.[10] With this model, Turing was able to answer two questions in
the negative:
Does a machine exist that can determine whether any arbitrary machine on
its tape is "circular" (e.g., freezes, or fails to continue its
computational task)?
Does a machine exist that can determine whether any arbitrary machine on
its tape ever prints a given symbol?[11][12]
Thus by providing a mathematical description of a *very simple device
capable of arbitrary computations,* he was able to prove properties of
computation in general—and in particular, the uncomputability of the
Entscheidungsproblem ('decision problem').[13]
<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
Brent
On 7/14/2024 2:02 PM, John Clark wrote:
On Sun, Jul 14, 2024 at 4:23 PM Brent Meeker <[email protected]>
wrote:
/> Every Turing machine can compute whatever is computable...which
means stopping with the answer. /
*
*
*Nonsense!We know everything that a one state Turing machine can due
to a blank input tape *
*because there are only 64 of them, some of them stop and some of them
never do. And w**e know everything that a two state Turing machine can
do to a blank input tape **because there are **20,736** of them.
**20,736 is larger than 64 therefore there must be some things that a
**two state Turing machine can do that a one **state Turing machine
can NOT do. *
John K Clark See what's on my new list at Extropolis
<https://groups.google.com/g/extropolis>
3e4
--
You received this message because you are subscribed to the Google
Groups "Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send
an email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/everything-list/CAJPayv1yQvDtCG_61pjNnSYoGkHZhmgJcAcG3zisDqPVrzX_Dw%40mail.gmail.com
<https://groups.google.com/d/msgid/everything-list/CAJPayv1yQvDtCG_61pjNnSYoGkHZhmgJcAcG3zisDqPVrzX_Dw%40mail.gmail.com?utm_medium=email&utm_source=footer>.
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/everything-list/95dfd483-52d4-4cb1-916d-0c29eccf86a1%40gmail.com.
