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 a computation in
terms of a computable function we can always arrive at the same computable
function 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 thesis claims
that all computations can be done by a universal turing machine, not merely
that they lead to the same class of computable functions (if "converted"
The latter is a far weaker statement, since computable functions abstract
from many relevant things about the machine.

And even this weaker statement doesn't seem true with regards to more
powerful models like super-recursive functions, as computable functions just
give finite results, while super-recursive machine can give
infinite/unlimited results.


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?

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 uses the
>> alphabet {1,0} and a universal turing machine B that uses the alphabet
>> {-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 value and
>> encoded 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 mentioned computable
functions just as means of explaining it, not as part of its definition.

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 of
Why are two machines that can be used to emlate each other regarded to be
In my view, there is a big difference between computing the same and being
able to emulate each other. Most importantly, emulation only makes sense
relative to another machine that is being emulated, and a correct


View this message in context:
Sent from the Everything List mailing list archive at

You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to
To unsubscribe from this group, send email to
For more options, visit this group at

Reply via email to