since 07 November 2024 :

View(s) :

3 (0 ULiège)

Download(s) :

0 (0 ULiège)

Recognising the Infinite Cycle

A Way of Looking at the Halting Problem

p. 21-42

Abstract

The formulations of the undecidability of the Halting Problem assume that the computing process being observed, the description of which is given on the input of the 'observing' Turing Machine, is the exact copy of the computing process running in the observing Turing Machine itself (Cantor's diagonal argument). By this way an analogue of stationary state in thermodynamic sense or an infinite cycle in computing sense is created, shielding now what is to be possibly discovered - the infinite cycle in the observed computing process for a 'normal' input. This shield is the real result of Cantor's diagonal argument which has been used for solving the Halting Problem. We believe that it is possible to recognize the infinite cycle, but with a time delay or staging in evaluating the trace of the observed computing process. Furthermore, the control unit of any Turing Machine is a finite automaton. Both these facts enable that the Pumping Lemma in the observing Turing Machine is usable and the general configuration types are constructed for the observed Turing Machine. This enables (in finite time) us (the observing Turing Machine) to recognize that the computing process in the observed Turing machine has entered into an infinite cycle. These ideas differ from Cantor's diagonal argument.

Text

Download Facsimile [PDF, 8.9M]

References

Bibliographical reference

Bohdan Hejna, « Recognising the Infinite Cycle », CASYS, 28 | 2014, 21-42.

Electronic reference

Bohdan Hejna, « Recognising the Infinite Cycle », CASYS [Online], 28 | 2014, Online since 10 October 2024, connection on 27 December 2024. URL : http://popups.uliege.be/3041-539x/index.php?id=4364

Author

Bohdan Hejna

Institute of Chemical Technology Prague, Department of Mathematics, Studentská 6, 166 28 Prague 6, Czech Republic

By this author

Copyright

CC BY-SA 4.0 Deed