[FOM] Simple historical question

[Rupert McCallum]

Presumably the history of the concept of undecidability is relevant
here. Once you have Turing's theorem that the halting problem is
undecidable, and Goedel's result (in his 1931 paper) that primitive
recursive relations are arithmetical, then the result follows easily. 

--- Michael Sheard <msheard at stlawu.edu> wrote:

> A question which I suspect some of the historically knowledgeable 
> members of the list may be able to answer easily:
> 
> To whom should we rightly give first credit for the
> result/observation 
> that Th(N,0,S,+,*,<) is undecidable?
> 
> Of the logic textbooks on my shelf, about half derive it as an easy 
> corollary of Godel's Incompleteness theorem; about half derive it as
> an 
> even easier corollary of Church's Undecidability theorem. 
> Remarkably, 
> one textbook apparently never states the result explicitly at all,
> but 
> then later uses it to derive the corresponding result about
> Th(Z,...).   
> None of the books supply a historical reference.  The best on-line 
> resource I could fine simply described the result as "following from
> the 
> work of Godel and Church."
> 
> This question arose in a pedagogical context.  In a survey of 
> undecidability results, I find it much simpler and more effective to 
> mention the undecidability of Th(N,...) rather than of PA, or any
> other 
> axiomatized theory, especially for a general audience.
> 
> Many thanks,
> Michael Sheard
> 
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
> 



       
____________________________________________________________________________________
Get the free Yahoo! toolbar and rest assured with the added security of spyware protection.
http://new.toolbar.yahoo.com/toolbar/features/norton/index.php