On 07 Sep 2012, at 12:24, benjayk wrote:

## Advertising

Bruno Marchal wrote:On 28 Aug 2012, at 21:57, benjayk wrote:It seems that the Church-Turing thesis, that states that an universal turing machine can compute everything that is intuitively computable, has near universal acceptance among computer scientists.Yes indeed. I think there are two strong arguments for this. The empirical one: all attempts to define the set of computable functions have led to the same class of functions, and this despite the quite independent path leading to the definitions (from Church lambda terms, Post production systems, von Neumann machine, billiard ball, combinators, cellular automata ... up to modular functor, quantum topologies, quantum computers, etc.).OK, now I understand it better. Apparently if we express acomputation interms of a computable function we can always arrive at the samecomputablefunction using a different computation of an abitrary turing universal machine. That seems right to me.But in this case I don't get why it is often claimed that CT thesisclaimsthat all computations can be done by a universal turing machine, notmerelythat they lead to the same class of computable functions (if"converted"appriopiately).

`This is due to a theorem applying to all universal programming`

`language, or universal system. They all contain a universal machine.`

`This makes CT equivalent with the thesis that there is a universal`

`machine with respect to (intuitive) computability.`

`It entails also an intensional Church thesis. Not only all universal`

`system can compute what each others can compute, but they can compute`

`the function in the same manner. This comes from the fact that a game`

`of life pattern (say) can exist and compute the universal function of`

`some other universal system, like a lisp interpreter for example. This`

`makes all result on computations working also on the notions of`

`simulation and emulation.`

The latter is a far weaker statement, since computable functionsabstractfrom many relevant things about the machine. And even this weaker statement doesn't seem true with regards to morepowerful models like super-recursive functions, as computablefunctions justgive finite results, while super-recursive machine can give infinite/unlimited results.

Computability concerns finite or infinite generable things.

`Then you can weaken comp indeed, and many results remains valid, but`

`are longer to prove. I use comp and numbers as it is easier.`

Bruno Marchal wrote:The conceptual one: the class of computable functions is closed for the most transcendental operation in math: diagonalization. This is not the case for the notions of definability, provability, cardinality, etc.I don't really know what this means. Do you mean that there are just countable many computations? If yes, what has this do with whether all universal turing machines are equivalent?

`It means that the notion of computability, despite being epistemic, is`

`well defined in math. It is the only such notion. The diagnonalization`

`cannot been applied to find a new computable function already not in`

`the class of the one given by any universal machine.`

`It makes comp far more explanatively close than any concept in math`

`and physics.`

Bruno Marchal wrote:I really wonder why this is so, given that there are simple cases where we can compute something that an abitrary turing machine can not compute using a notion of computation that is not extraordinary at all (and quite relevant in reality).For example, given you have a universal turing machine A that usesthealphabet {1,0} and a universal turing machine B that uses thealphabet{-1,0,1}. Now it is quite clear that the machine A cannot directly answer any questions that relates to -1. For example it cannot directly compute-1*-1=1. Machine A can only be used to use an encoded input valueandencoded description of machine B, and give an output that is correct given the right decoding scheme. But for me this already makes clear that machine A is less computationally powerful than machine B.Church thesis concerns only the class of computable functions.Hm, maybe the wikipedia article is a bad one, since it mentionedcomputablefunctions just as means of explaining it, not as part of itsdefinition.Bruno Marchal wrote:The alphabet used by the Turing machine, having 1, 2, or enumerable alphabet does not change the class. If you dovetail on the works of 1 letter Turing machine, you will unavoidably emulate all Turing machines on all finite and enumerable letters alphabets. This can be proved. Nor does the number of tapes, and/or parallelism change that class. Of course, some machine can be very inefficient, but this, by definition, does not concern Church thesis.Even so, CT thesis makes a claim about the equivalence of machines,not ofemulability.

`It does, by the intensional CT, which follows easily by the`

`"enumeration theorem", which is the standard name asserting the`

`existence of universal machine in each such universal class of`

`computable functions.`

Why are two machines that can be used to emlate each other regardedto beequivalent?

`They are equivalment with respect of the computability/emulability`

`issue, but not on provability, knowability, sensibility, etc. Thay`

`might still argue about which movie to look on TV!`

In my view, there is a big difference between computing the same andbeingable to emulate each other. Most importantly, emulation only makessenserelative to another machine that is being emulated, and a correct interpretation.

By the intensional CT, emulation is like computation. Bruno

benjayk -- View this message in context: http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34401986.html Sent from the Everything List mailing list archive at Nabble.com. --You received this message because you are subscribed to the GoogleGroups "Everything List" group.To post to this group, send email to everything-list@googlegroups.com.To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com.For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.

http://iridia.ulb.ac.be/~marchal/ -- You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.