Universality in two dimensions

Abstract : Turing, in his immortal 1936 paper, observed that '[human] computing is normally done by writing... symbols on [two- dimensional] paper', but noted that use of a second dimension 'is always avoidable' and that 'the two-dimensional character of paper is no essential of computation'. We propose to promote two-dimensional models of computation and exploit the naturalness of two-dimensional representations of data. In particular, programs for a two-dimensional Turing machine can be recorded most naturally on its own two-dimensional input-output grid in such a transparent fashion that schoolchildren would have no difficulty comprehending their behaviour. This two-dimensional rendering allows, furthermore, for a most perspicacious rendering of Turing's universal machine.
Type de document :
Article dans une revue
Journal of Logic and Computation, Oxford University Press (OUP), 2013, 〈10.1093/logcom/ext022〉
Liste complète des métadonnées

Littérature citée [47 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00919604
Contributeur : Gilles Dowek <>
Soumis le : mardi 17 décembre 2013 - 09:46:34
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : lundi 17 mars 2014 - 22:26:03

Fichier

universality2d.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Collections

Citation

Nachum Dershowitz, Gilles Dowek. Universality in two dimensions. Journal of Logic and Computation, Oxford University Press (OUP), 2013, 〈10.1093/logcom/ext022〉. 〈hal-00919604〉

Partager

Métriques

Consultations de la notice

224

Téléchargements de fichiers

337