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

Aatu Koskensilta aatu.koskensilta at xortec.fi
Wed Jan 7 01:21:18 EST 2004

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

More information about the FOM mailing list