On Sat, Jul 13, 2024, 6:22 PM John Clark <[email protected]> wrote:
> On Sat, Jul 13, 2024 at 4:29 PM Brent Meeker <[email protected]> > wrote: > > *> All Turing machines have the same computational capability. * > > > Well that certainly is not true! There is a Turing Machine for any > computable task, but any PARTICULAR Turing Machine has a finite number of > internal states and can only do one thing. If you want something else done > then you are going to have to use a Turing Machine with a different set > of internal states. > The number of internal states a Turing machine has is unrelated to a Turing machine's universality. Think of internal states as the instruction set in a CPU. A CPU can only be in so many states, but pair it with a memory and a loop, and it can compute anything. I think what you are saying makes sense if you consider a Turing machine running a particular fixed program. Then the Turing machine acts like some particular machine. And if you want it to act differently, you need to provide a different program. Jason > > The number of n-state 2-symbol Turing Machines that exist is (4(n+1))^(2n), > This is because there are n-1 non-halting states, and we have n choices > for the next state, and 2 choices for which symbol to write, and 2 > choices for which direction to move the read head. So for example there > are 16,777,216 different three state Turing Machines, and 25,600,000,000 > different four state turing machines. > > John K Clark See what's on my new list at Extropolis > <https://groups.google.com/g/extropolis> > nrp > > -- > 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/CAJPayv12iBKidY_a_QC4tvTtdFNdmZRgZ9K-UH0La%3DTvdUMuew%40mail.gmail.com > <https://groups.google.com/d/msgid/everything-list/CAJPayv12iBKidY_a_QC4tvTtdFNdmZRgZ9K-UH0La%3DTvdUMuew%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/CA%2BBCJUjjZ3t7kcDeKAfz3seZC%2BK6NpEQffZJ18v4PW%2BoD%3Do23A%40mail.gmail.com.
