**From:** Christian Szegedy (*szegedy@or.uni-bonn.de*)

**Date:** Mon Aug 16 2004 - 04:42:00 MDT

**Next message:**Christian Szegedy: "Re: Final draft of my philosophical platform now on line"**Previous message:**Alton Sartor: "Some insite from the denizens of the net"**In reply to:**Marc Geddes: "Re: Final draft of my philosophical platform now on line"**Next in thread:**Marc Geddes: "Re: Final draft of my philosophical platform now on line"**Reply:**Marc Geddes: "Re: Final draft of my philosophical platform now on line"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

*>"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.

**Next message:**Christian Szegedy: "Re: Final draft of my philosophical platform now on line"**Previous message:**Alton Sartor: "Some insite from the denizens of the net"**In reply to:**Marc Geddes: "Re: Final draft of my philosophical platform now on line"**Next in thread:**Marc Geddes: "Re: Final draft of my philosophical platform now on line"**Reply:**Marc Geddes: "Re: Final draft of my philosophical platform now on line"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

*
This archive was generated by hypermail 2.1.5
: Wed Jul 17 2013 - 04:00:48 MDT
*