Re: Yet another Attempt at Disproving the Halting Problem

From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 08/14/04 

Date: 14 Aug 2004 14:14:27 -0700

>parr\(*> says...

Or may I call you "Laury"?

>Out of interest, do you think any currently produced real computers
>are Turing Complete? I don't think so because they can' have
>infinite length 'tapes'. Again, I could have misunderstood.

Yes, that's right. In C, you can only refer to a limited number
of machine locations (although, really, really, huge).

However, an actual program together with floppy disks is Turing
complete: whenever the program runs out of space it just asks
the user to please enter the next floppy disk. (Or "please enter
the previous floppy disk"). If the user is kindly keeping track
of the order of the floppies, that makes an actual program into
a kind of Turing machine in which one "square of the tape" is
an entire floppy disk, and instead of just two symbols 1 and 0,
it has 10^10^10 symbols (however many possible floppy disk states
there are). 

--
Daryl McCullough
Ithaca, NY

Relevant Pages