Informatica 21 (3):425–454 (2010)

Yaroslav Sergeyev
Università della Calabria
The Turing machine is one of the simple abstract computational devices that can be used to investigate the limits of computability. In this paper, they are considered from several points of view that emphasize the importance and the relativity of mathematical languages used to describe the Turing machines. A deep investigation is performed on the interrelations between mechanical computations and their mathematical descriptions emerging when a human (the researcher) starts to describe a Turing machine (the object of the study) by different mathematical languages (the instruments of investigation). Together with traditional mathematical languages using such concepts as ‘enumerable sets’ and ‘continuum’ a new computational methodology allowing one to measure the number of elements of different infinite sets is used in this paper. It is shown how mathematical languages used to describe the machines limit our possibilities to observe them. In particular, notions of observable deterministic and non-deterministic Turing machines are introduced and conditions ensuring that the latter can be simulated by the former are established.
Keywords Theory of automatic computations  observability of Turing machines  relativity of mathematical languages  infinite sets  Sapir-Whorf thesis
Categories (categorize this paper)
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Translate to english
Revision history

Download options

PhilArchive copy

 PhilArchive page | Other versions
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 N Tscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Non-Standard Analysis.Abraham Robinson - 1961 - North-Holland Publishing Co..

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Accelerating Turing Machines.B. Jack Copeland - 2002 - Minds and Machines 12 (2):281-300.
Alan Turing and the Mathematical Objection.Gualtiero Piccinini - 2003 - Minds and Machines 13 (1):23-48.
Transcending Turing Computability.B. J. Maclennan - 2003 - Minds and Machines 13 (1):3-22.
Supermachines and Superminds.Eric Steinhart - 2003 - Minds and Machines 13 (1):155-186.
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.
Turing’s Responses to Two Objections.Darren Abramson - 2008 - Minds and Machines 18 (2):147-167.
The Broad Conception of Computation.Jack Copeland - 1997 - American Behavioral Scientist 40 (6):690-716.
Infinite Time Turing Machines.Joel David Hamkins & Andy Lewis - 2000 - Journal of Symbolic Logic 65 (2):567-604.


Added to PP index

Total views
54 ( #212,156 of 2,519,863 )

Recent downloads (6 months)
15 ( #52,840 of 2,519,863 )

How can I increase my downloads?


My notes