On Sun, Jul 14, 2024 at 9:35 AM Quentin Anciaux <allco...@gmail.com> wrote:
*> I think you miss the difference between UTM, Universal turing machine > and turing machine...* > > *https://cs.stackexchange.com/questions/69197/difference-between-turing-machine-and-universal-turing-machine#:~:text=A%20Turing%20machine%20can%20be,input%20and%20generates%20some%20output > <https://cs.stackexchange.com/questions/69197/difference-between-turing-machine-and-universal-turing-machine#:~:text=A%20Turing%20machine%20can%20be,input%20and%20generates%20some%20output>.* > *It says "**A UTM can be compared to a computer. It can take any program and run it with some input and generates some output", and I agree with that, PROVIDED that the tape, in addition to containing the program you wish to run, ALSO contains information about the sort of computer the program is to be run on, that is to say it defines and specifies the set of internal states the T**uring Machine** will have. Thus a** UTM can emulate an Apple, Windows, LINUX, or any other type of digital computer if it is given the correct set of internal states. And it's important to remember that the very definition of "a different Turing Machine" is a machine with a different set of internal states. A Universal Turing Machine has the ability to turn into any Turing Machine if the information on how to do that is included in the input tape. * John K Clark See what's on my new list at Extropolis <https://groups.google.com/g/extropolis> > *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. * >> >> -- 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/CAJPayv1LOPhmLU3PZjA_b-GLdXxMsivEWbiUthg92piymR5J2g%40mail.gmail.com.
