From: Christian Szegedy (szegedy@or.uni-bonn.de)
Date: Mon Aug 16 2004 - 04:42:00 MDT
>"But since the entire physical world is described by
>mathematical equations, Turing's conception of a
>'Universal Turing Machine' (the general purpose
>computer) suggests that all of reality is entirely
>computational, in the sense that any finite part of
>reality can be simulated by a general purpose
>computer."
>
>Please tell me why I am wrong.
>
There are methamatically definable functions that are
not Turing computable. For example the function
defined by the halting problem is a well-known example
for that:
Let T be a fixed universal Turing machine. For a sequence
s of bits let f(s)=true if T stops on input s, false otherwise.
Function f is clearly well-defined, and it is simple to see that
it is not Turing computable.
A lot of people without minimal mathematical background
tend to mistake the notion of "universal Turing machine".
It does *not* refer to a machine which can perform any
computation that is mathemtically (or physically) definable
(or achievable).
A universal Turing machine is simply a machine which can
simulate any other Turing machine when provided with
suitable input.
Whether the current physics allows for building any
deterministic machine transforming discrete inputs to
a discrete outputs computing a Turing-noncomputable
function is an open question. Generally, it is a hard question
even we fix the rules of physics. I am not aware of an exact
proof for the nonexistence of such machines even
in the Newton meachanics.
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:48 MDT