A Natural Axiomatization of Church's Thesis

From: Jef Allbright <jef.domain.name.hidden>
Date: Fri, 13 Jul 2007 14:39:09 -0700

Apropos much discussion on this list, a new paper is available at

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

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:14 PST