On 7/15/2024 5:28 AM, John Clark wrote:
On Sun, Jul 14, 2024 at 9:00 PM Brent Meeker <[email protected]>
wrote:
//
/> What's your definition of a Turing machine? /
*A Turing Machine is the simplest possiblecomputer modelthat the
logical operation of any real computer can be reduced to if given
enough internal states, it has n States plus the HALT state. A Turing
Machineconsists of two parts, a long tape with zeros and ones on it
and a read/write head which can only print a zero or a one on the
tape, move one notch left or right, and CHANGE INTO A DIFFERENT STATE.
After the head has read a symbol what it will do next depends on
whether it has just seen a one or a zero, and it depends ON WHAT STATE
IT IS CURRENTLY IN. And in general, the more states a Turing Machine
can be in the richer and more complex its behavior will be. *
*An easy way to understand Turing Machines is to separate the program
and the data. The data is on the tape and the program is on a series
of cards. You always start at card #1 and, depending on if you are
reading a 1 or a 0 on the tape that card tells you to print a one or
a zero, move left or right, and it instructs you on which state to
turn into next, that is to say it tells you the number of the card
(a.k.a. state) to read (a.k.a. be in) next. As I said, all Turing
Machines have N states plus a HALT state. The information on the cards
could have originally come from the tape as in a Universal Turing
Machine, but for simplicity I will assume the cards have already been
pre-installed. *
**
*For a start let's look at a one state (card) Turing Machine, there
are 8 different actions a card could tell you to perform if you first
see a zero on the tape :
1) Write a 1 or a 0.
2) Move left or right.
3) Stay on card#1 (the only card) or halt.*
*
So there are 2^3=2*2*2 =8 things you can do if you read a zero. But
there are also 8 things you can do if you first read a 1 on the tape,
so there are 8*8= 64 possible one card (aka one state) Turing
Machines. 64 is a small number so you can't do much with just a one
state Turing Machine.
*
*
*
*Now let’s look at a 2 card (state) Turing Machine, if you’re
currently reading 0 there are 12 things the first card could tell you
to do; write a zero or a one, shift left or right, go into state
(card) 1 or card 2 or halt, 2*2*3= 12. And if you’re currently
reading 1 there are also 12 things the first card could tell you to
do: So there are 12*12=144 different things that first card could
tell you to do. However, each of those 144 cards must be paired up
with a second card, and there are also 144 things that the second card
could tell you to do. So there are 144*144= 20,736 different 2 card
(state) Turing Machines.*
*
*
*The general formula is, there are (2 N s +1)^(s N )Turing machines
with N states and with s symbols. A two symbol machine is the simplest
and can do everything a machine with more symbols can do, so if s=2
then the formula for the number of 2 symbol N state (card) Turing
Machines) is [4(N+1)]^(2N). Thus the number of Turing Machines
increases exponentially with N, but the Busy Beaver number increases
far far faster than exponentially, faster than super-exponential, in
fact the function is not even computable despite the fact it's well
defined and finite.*
> /I posted the definition from Wikipedia:
/
*Thanks but I already figured out how to look things up in Wikipedia.*
*Knowing how to see what it says isn't the same as knowing what it says:
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./
Brent
*
*
*
John K Clark See what's on my new list at Extropolis
<https://groups.google.com/g/extropolis>
wlo
--
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/CAJPayv1EbqrUAsxA9603O8NDg5_A42B2_WW14mS_rEiwztNoGg%40mail.gmail.com
<https://groups.google.com/d/msgid/everything-list/CAJPayv1EbqrUAsxA9603O8NDg5_A42B2_WW14mS_rEiwztNoGg%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/831020d1-5977-49e5-8e07-7a0c035f91df%40gmail.com.
