Arithmetic logical Irreversibility and the Turing's Halt Problem


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 (deleting, logical or arithmetic operations) and defining a new concept of arithmetic logical irreversibility and memory erasure that generate uncertainty and computational improbability due to loss of information during these events. Different computational steps (input) may 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 .



External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

  • Only published works are available at libraries.

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

63 (#191,442)

6 months
7 (#118,276)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Yair Lapin
Hebrew University of Jerusalem

Citations of this work

No citations found.

Add more citations

References found in this work

Computability & Unsolvability.Martin Davis - 1958 - Dover Publications.
An Unsolvable Problem of Elementary Number Theory.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (2):73-74.

Add more references