Computable Diagonalizations and Turing's Cardinality Paradox

A. N. Turing’s 1936 concept of computability, computing machines, and computable binary digital sequences, is subject to Turing’s Cardinality Paradox. The paradox conjoins two opposed but comparably powerful lines of argument, supporting the propositions that the cardinality of dedicated Turing machines outputting all and only the computable binary digital sequences can only be denumerable, and yet must also be nondenumerable. Turing’s objections to a similar kind of diagonalization are answered, and the implications of the paradox for the concept of a Turing machine, computability, computable sequences, and Turing’s effort to prove the unsolvability of the Entscheidungsproblem, are explained in light of the paradox. A solution to Turing’s Cardinality Paradox is proposed, positing a higher geometrical dimensionality of machine symbol-editing information processing and storage media than is available to canonical Turing machine tapes. The suggestion is to add volume to Turing’s discrete two-dimensional machine tape squares, considering them instead as similarly ideally connected massive three-dimensional machine information cells. Three-dimensional computing machine symbol-editing information processing cells, as opposed to Turing’s two-dimensional machine tape squares, can take advantage of a denumerably infinite potential for parallel digital sequence computing, by which to accommodate denumerably infinitely many computable diagonalizations. A three-dimensional model of machine information storage and processing cells is recommended on independent grounds as better representing the biological realities of digital information processing isomorphisms in the three-dimensional neural networks of living computers
Keywords Cantor, Georg  Cardinality  Computability  Computable sequence  Denumerability, nondenumerability  Diagonalization   Entscheidungsproblem  Löwenheim-Skolem theorem  Skolem paradox  Turing, A. N.  Universal Turing machine
Categories (categorize this paper)
DOI 10.1007/s10838-014-9244-x
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 39,566
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Infinite Time Turing Machines.Joel David Hamkins - 2002 - Minds and Machines 12 (4):567-604.
A Note on the Entscheidungsproblem.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (1):40-41.

View all 19 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Accelerating Turing Machines.B. Jack Copeland - 2002 - Minds and Machines 12 (2):281-300.
Turing's Golden: How Well Turing's Work Stands Today.Justin Leiber - 2006 - Philosophical Psychology 19 (1):13-46.
Alan Turing and the Foundations of Computable Analysis.Guido Gherardi - 2011 - Bulletin of Symbolic Logic 17 (3):394-430.
Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
Beyond the Universal Turing Machine.Jack Copeland - 1999 - Australasian Journal of Philosophy 77 (1):46-67.
Is There a Nonrecursive Decidable Equational Theory?Benjamin Wells - 2002 - Minds and Machines 12 (2):301-324.
Transcending Turing Computability.B. Maclennan - 2003 - Minds and Machines 13 (1):3-22.
Is the Human Mind a Turing Machine?D. King - 1996 - Synthese 108 (3):379-89.
Infinite Time Turing Machines.Joel David Hamkins - 2002 - Minds and Machines 12 (4):567-604.


Added to PP index

Total views
31 ( #244,667 of 2,325,859 )

Recent downloads (6 months)
3 ( #523,443 of 2,325,859 )

How can I increase my downloads?


My notes

Sign in to use this feature