Towards a Church-Turing-Thesis for Infinitary Computations

Por • 3 ago, 2013 • Sección: Ciencia y tecnología

Merlin Carl

Abstract: We consider the question whether there is an infinitary analogue of the Church-Turing-thesis. To this end, we argue that there is an intuitive notion of transfinite computability and build a canonical model, called Idealized Agent Machines ($IAM$s) of this which will turn out to be equivalent in strength to the Ordinal Turing Machines defined by P. Koepke.

arXiv:1307.6599v1 [math.LO]

Post to Twitter

Etiquetado con: , , ,

Escribe un comentario