Re: Arthur O'Dwyer on the feasibility of simulating a Turing Machine

From: Edward G. Nilges (spinoza1111_at_yahoo.com)
Date: 02/27/04 

Date: 27 Feb 2004 01:58:49 -0800

Willem <willem@stack.nl> wrote in message news:<slrnc3rias.2t7j.willem@toad.stack.nl>...
> Edward wrote:
> ) There seems to be a consensus here that a computer program CANNOT BE
> ) WRITTEN to simulate a Turing Machine, and this consensus is wrong:
> ) this post shall prove it so.
> )
> ) <snip repeat of another poster's idea to have the program grow across
> ) the internet>
>
> This has already shown to be false; there's only a finite amount of matter
> in the universe.

However, do we know if there is a finite amount of time? For by simply
having the simulator act as a sort of virus we can exchange raum for
zeit, space for time.
>
> A theoretical TM could be written that can capture the state of the entire
> universe. This TM can obviously not be contained within the universe.
> Assuming that computer programs have to exist within the universe, a Turing
> Machine exists that cannot be simulated by a computer program.

I'm not so sure. Given a suitable encoding (say a high exponent power
series suffixed with descending powers until the exact value is found
such as n*2^2^....2+m*2^....+x*2^0 you could always encode the number
of the TM being represented. But as I say I am not sure.

Or you could again replace time by space and agree to allow the TM to
output the state of the universe over time.

I am sure the issue is more complex than presented.
>
>
> SaSW, Willem

Relevant Pages