Universality in two dimensions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Journal of Logic and Computation Année : 2013

Universality in two dimensions

Résumé

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.
Fichier principal
Vignette du fichier
universality2d.pdf (1.2 Mo) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-00919604 , version 1 (17-12-2013)

Identifiants

Citer

Nachum Dershowitz, Gilles Dowek. Universality in two dimensions. Journal of Logic and Computation, 2013, ⟨10.1093/logcom/ext022⟩. ⟨hal-00919604⟩

Collections

INRIA INRIA2
100 Consultations
470 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More