On Sun, Jul 14, 2024 at 9:00 PM Brent Meeker <meekerbr...@gmail.com> wrote:
* > What's your definition of a Turing machine? * > *A Turing Machine is the simplest possible computer model that 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 Machine consists 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.* 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 everything-list+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/everything-list/CAJPayv1EbqrUAsxA9603O8NDg5_A42B2_WW14mS_rEiwztNoGg%40mail.gmail.com.
