On 7/13/2024 3:21 PM, John Clark 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.
Or a different tape/program.
"A Turing machine is a mathematical model of computation describing an
abstract machine that manipulates symbols on a strip of tape according
to a table of rules.Despite the model's simplicity, it is /capable of
implementing any computer algorithm./"
Brent
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 differentfour 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/84d558fb-d7d8-41b8-8436-997632a25249%40gmail.com.
