Yair Lapin
Hebrew University of Jerusalem
A new approach to the halting problem of the Turing machine using different interpretations of the Shannon measure of the information on the computational process represented as a distribution of events and defining a new concept of arithmetic logical irreversibility and memory erasure that generate uncertainty and computational improbability due to loss of information during computation. Different computational steps (input) can give the same result (next step, output) introducing thus information entropy in the computing process and uncertainty about the original step (cause). This means that the same output may be produced by different inputs. Global indeterminism of computation as distribution but determinism of the computation as current process because the outputs are the same but the information not. The program or Turing machine as macro description of the computational states as micro description that they may be several and different but give the same result when they work .
Keywords Turing Halt problem  Gödel Theorem  Information Theory  Algorithmic information theory  Decision problem
Categories (categorize this paper)
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
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

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

A Mathematical Model of Quantum Computer by Both Arithmetic and Set Theory.Vasil Penchev - 2020 - Information Theory and Research eJournal 1 (15):1-13.
The Annotation Game: On Turing (1950) on Computing, Machinery, and Intelligence.Stevan Harnad - 2006 - In Robert Epstein & Grace Peters (eds.), [Book Chapter] (in Press). Kluwer Academic Publishers.
Accelerating Turing Machines.B. Jack Copeland - 2002 - Minds and Machines 12 (2):281-300.
Busy Beaver Competition and Collatz-Like Problems.Pascal Michel - 1993 - Archive for Mathematical Logic 32 (5):351-367.
Non-Turing Computers and Non-Turing Computability.Mark Hogarth - 1994 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1994:126-138.
Almost Everywhere Domination.Natasha L. Dobrinen & Stephen G. Simpson - 2004 - Journal of Symbolic Logic 69 (3):914-922.
Turing's Golden: How Well Turing's Work Stands Today.Justin Leiber - 2006 - Philosophical Psychology 19 (1):13-46.


Added to PP index

Total views
35 ( #315,165 of 2,462,871 )

Recent downloads (6 months)
35 ( #24,962 of 2,462,871 )

How can I increase my downloads?


My notes