Logical Approaches to Computational Barriers

Decidability of arithmetic through hypercomputation: logical objections

THIS TALK IS CANCELLED!!! | |

Speaker:
| Paolo Cotogno |

The theory of hypercomputation aims to extend effective computability beyond Turing reducibility, in particular by means of supertasks; physical models are considered in Newtonian, relativistic and quantum contexts. Apart from implementation differences, all approaches take for granted that supertask computations would decide arithmetic; in logical terms, this amounts to assume that the undecidability of Peano Arithmetic can be bypassed by the omega-rule. We argue that this assumption is untenable, as long as the system is consistent: the conclusion follows from alternative versions of Gödel’s incompleteness, such as Rosser’s and Yablo’s, which are indifferent to infinite deductions.

websites: Arnold Beckmann | 2006-06-30 |