[FOM] Re: Comment on Church's Thesis (Harvey Friedman)

[Aatu Koskensilta]

addamo wrote:

>I don't understand how your comment refers to Church's Thesis.
>Could you make it more explicit?
>
>Do you or anybody know a proof of the undecidability of the Halting problem
>not depending on Church's Thesis? 
>  
>
It's not clear how there could be any. Without Church's thesis all you 
can do is to show
the Halting problem undecidable by means of the class of functions 
defined by e.g. Turing
machines, lambda expressions, formulae defining functions by recursion, 
and what not. Church's
Thesis licenses you to infer the absolute undecidability of the Halting 
problem from this.

-- 
Aatu Koskensilta (aatu.koskensilta at xortec.fi)

"Wovon man nicht sprechen kann, daruber muss man schweigen"
 - Ludwig Wittgenstein, Tractatus Logico-Philosophicus