On Sat, Jul 13, 2024 at 10:34 PM Brent Meeker <meekerbr...@gmail.com> wrote:
*> The machine is universal. You don't need a different machine with > different internal states.* *First of all, the very definition of "a different Turing Machine" is a machine with a different set of internal states*. And there is not just one Turing machine, there are an *infinite* number of them. *There are 64 one state two symbol (zero and one) Turing Machines, 20,736 two state, **16,777,216 three state, **25,600,000,000 four state, and **634,033,809,653,824 five state two symbol T**uring Machines. * A Turing Machine with different sets of* internal states** will exhibit** different behavior even if given identical input states. *I think What confuses you is that it is possible to have a machine in which the tape not only provides the program the machine should work on but also the set of internal states that the machine has. In a way you could think of the tape as providing not only the program but also the wiring diagram of the computer. A universal Turing Machine is in an undefined state until the input tape, *or something else*, puts it in one specific state. *Consider the Busy beaver function, if you feed in a tape with all zeros on it into all 4 state Turing Machines and ask "which of those 25,600,000,000 machines will print the most ones before stopping" (it's important that the machine eventually stops), you will find this is not an easy question. All the machines are operating on identical input tapes (all zeros) but they behave differently, some stop almost immediately, others just keep printing 1 forever, but for others the behavior is vastly more complicated. It turns out that the winner is a set of states that prints out 13 ones after making 107 moves. * *A five state Turing Machine behaves differently, we just found out that a particular set of internal states prints 2098 ones after making 47,176,870 moves. I wouldn't be surprised if the sixth Busy Beaver number is not computable, we know for a fact that any busy beaver number for a 745 State Turing machine or larger is not computable. Right now all we know about BB(6) is that it's larger than 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10.* *The point of all this is that Turing Machines with different sets of internal states behave very differently. * John K Clark See what's on my new list at Extropolis <https://groups.google.com/g/extropolis> mth > -- 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/CAJPayv1NX6MaOW7eJo1TVbmpAfvb7k4CgvnYOGV%3DzfDt%2BpOo1w%40mail.gmail.com.
