Skip to Main content Skip to Navigation
Journal articles

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 metadata

Cited literature [47 references]  Display  Hide  Download
Contributor : Gilles Dowek Connect in order to contact the contributor
Submitted on : Tuesday, December 17, 2013 - 9:46:34 AM
Last modification on : Friday, January 21, 2022 - 3:16:01 AM
Long-term archiving on: : Monday, March 17, 2014 - 10:26:03 PM


Publisher files allowed on an open archive




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



Les métriques sont temporairement indisponibles