Apropos much discussion on this list, a new paper is available at
<ftp://ftp.research.microsoft.com/pub/tr/TR-2007-85.pdf>

Abstract:
The Abstract State Machine Thesis asserts that every classical
algorithm is behaviorally equivalent to an abstract state machine.
This thesis has been shown to follow from three natural postulates
about algorithmic computation. Here, we prove that augmenting those
postulates with an additional requirement regarding basic operations
implies Church's Thesis, namely, that the only numeric functions that
can be calculated by effective means are the recursive ones (which are
the same, extensionally, as the Turing-computable numeric functions).
In particular, this gives a natural axiomatization of Church's Thesis,
as Gödel and others suggested may be possible.

- Jef

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

Reply via email to