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 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.
