[FOM] Re: Comment on Church's Thesis (Harvey Friedman)
aatu.koskensilta at xortec.fi
Wed Jan 7 01:21:18 EST 2004
>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