Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Decidability of arithmetic through hypercomputation: logical objections

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