Re: Poll: Are PCs Turing Machines?

From: |-|erc (h_at_r.c)
Date: 12/09/04 

Date: Thu, 9 Dec 2004 23:05:45 +1000

> Define TM as algorithm+actuation_device.
>
> Is a PC an algorithm with some actuation device to run that algorithm? YES!

Examine the more relevant question, is a PC equivalent to a turing machine?

This means, is any given PC equivalent to some turing machine?

How is this possible? Because all the components of a TM have a physical
equivalent except for the infinite tape, but not all TM's require the infinite tape.

Say we construct a TM that uses a finite amount of memory. Its not a trivial machine
that only requires 10 tape cells no matter the input, it has usual complexity requirements
and uses more memory with bigger inputs. (Windows)

      STATE COMPONENT
                v pointer
|_0_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|

For the TM to behave like a PC, it must know when it is about to run out of memory.
Here's a solution.

      STATE COMPONENT
                v pointer
|_1_|_1_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|_1_|_1_|

Just like monkey flying to the end of the universe on his magic cloud, and writing grafitti
on the 5 pillars to show he had been to the end, on the larger scale of things, he actually
only went to the end of Buddhas arm and painted on her fingers, and decided of his own
accord to return again back into the realms of the possible.

The theoretical concept of infinite memory and a practical model are mutually satisfied.

We can use bitpairs on the tape with the following mapping
00 - 0
01 - 1
10 - ?
11 - EOF

and the TM moves over pair of digits to interpret them.

Now the state component can be set up with all the loaded software of the PC

One complication is interaction. The defn of the TM is that the input is laid out
on the tape before the 1st cycle. The only way a TM could read a keystroke
and respond to it is if this definition is relaxed. Its a bit tricky, especially with
a finite tape and an infinite input stream. The TM would have to point to somewhere
in memory where you can type in some data at that buffer space, scan it, clear it
and then point somewhere else. Functional programs achieve interaction with a
process(keyboard()) function, like so:

keyboard = <abc...>
map(keyboard) = <
<a>
<ab>
<abc>
..
>

process
  handle(first(1, map(keyboard())) <a>
  hande(first(2, map(keyboard())) <ab>
...

That way it can return a result to the keypress a, but still keep inside the function
and process <ab>, then <abc>. It looks like highly redundant data but the functional
parser handles it cleanly. This is called lazy evaluation, first(3, N) = <1 2 3>
will halt processing (and give a result) even though it has an infinite stream as a parameter.

Not all Turing Machines are PCs.
All PCs are Turing Machines.

Herc

Relevant Pages

  • Re: turing completeness
    ... claim that the tape *must* be infinite. ... >>The Turing Machine just needs to be able at will to drive to CompUsa ... computer runs out of memory its operating system aborts the TM ...
    (comp.programming)
  • Re: Poll: Are PCs Turing Machines?
    ... is a PC equivalent to a turing machine? ... equivalent except for the infinite tape, but not all TM's require the infinite tape. ... Say we construct a TM that uses a finite amount of memory. ...
    (comp.theory)
  • Re: Turing machines, quantum computers, and alephs
    ... >> Turing defined a Turing machine as having an infinite tape. ... the abstract quantum computer with infinitely many qubits might start ...
    (comp.programming)
  • Re: Turing machines, quantum computers, and alephs
    ... >> Turing defined a Turing machine as having an infinite tape. ... the abstract quantum computer with infinitely many qubits might start ...
    (sci.math)
  • Re: Turing machines, quantum computers, and alephs
    ... > number of tape segments, but if it starts with a blank tape, or a tape ... > the abstract quantum computer with infinitely many qubits might start ... > it seems no less finite in your sense than the abstract Turing machine ... > with its infinite but mostly zeroed tape. ...
    (comp.programming)