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 everything-list.domain.name.hidden.com
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden.com
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Fri Jul 13 2007 - 17:39:28 PDT