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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [47 references]  Display  Hide  Download

https://hal.inria.fr/hal-00919604
Contributor : Gilles Dowek <>
Submitted on : Tuesday, December 17, 2013 - 9:46:34 AM
Last modification on : Tuesday, January 1, 2019 - 6:46:02 AM
Long-term archiving on : Monday, March 17, 2014 - 10:26:03 PM

File

universality2d.pdf
Publisher files allowed on an open archive

Identifiers

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⟩

Share

Metrics

Record views

294

Files downloads

480