FOM: Various Church-Turing theses

[William Calhoun]

On Tue, 30 Jan 2001 JoeShipman at aol.com wrote:

> As far as CT-psych (intuitive computability) is concerned, I think the 
> identification of total recursive functions with intuitively computable 
> functions is more secure than the identification of partial recursive 
> functions with intuitively enumerable sets (or one-sided computable 
> functions).  The prescription "simultaneously for all N search for proofs 
> that the Nth Turing machine computation does not halt, extending your 
> mathematical axioms beyond ZFC using appropriate mathematical methods, and 
> outputting those N where a proof is found", while vague, could provide a 
> counterexample.
> 
> -- Joe Shipman

I don't know exacly how you define "intuitively enumerable", but to my
mind the example you give would not provide a counterexample.  If the way
of extending ZFC can be formalized as a computable process, then the set
of numbers enumerated would be computably enumerable.  If the way of
extending ZFC cannot be formalized as a computable process, then we
essentially have random decisions about how to extend ZFC.  (The phrase
"using appropriate mathematical methods"  doesn't make it clear how you
would decide when two ways of extending ZFC are both consistent.)  This
could generate a set that is not computably enumerable, but it is also not
"intuitively" COMPUTABLY enumerable.  CT says nothing about what sets
could be enumerated by random processes, only about what sets can be
enumerated by an algorithmic process. 

I find your speculations about whether there could exist nonrecursive
sequences in nature interesting, but that is irrelevant to CT as it was
conceived by Church and Turing.  I agree with Sazonov that CT is really a
mathematical definition of the intuitive notion of algorithmic process. 
Turing's analysis of the actions humans take in following an algorithm
goes a long way toward demonstrating that CT is the right definition.  The
equivalence of various models of computation makes it even more convincing
that Turing's analysis was correct. 

-Bill Calhoun 
-Math, CS, and Stats 	wcalhoun at planetx.bloomu.edu 
-Bloomsburg University 	Telephone: 570-389-4507 
-Bloomsburg, PA 17815 	FAX: 570-389-3599

Research Interest: Computability Theory