Information Thermodynamics and Halting Problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F60461373%3A22340%2F15%3A43900693" target="_blank" >RIV/60461373:22340/15:43900693 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.5772/59835" target="_blank" >http://dx.doi.org/10.5772/59835</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.5772/59835" target="_blank" >10.5772/59835</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Information Thermodynamics and Halting Problem

Popis výsledku v původním jazyce

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 &apos;observing&apos; Turing Machine, is, at any given moment, the exact copy of the computing process running in the observing machine itself . In this way an infinite cycle is created shielding what is to be possibly discovered, the possible infinite cycle in the observed computing process. By this type of our consideration and in the thermodynamic sense the equilibrium status of a certain thermodynamic system is described or, even created. This is a thermodynamic image of the Cantor diagonal method used for seeking a possible infinite cycle and which, as such, has the property of the Perpetuum Mobile, the structure of which is recognizable and therefore we can avoid it. Thus we can show that it is possible to recognize the infinite cycle as a certain original equilibrium, but with a &apos;step-aside&apos; or a time delay in evaluating the trace of the observed computing process. The trace is a record of the sequence of configurations of the observed Turing machine. These configurations can be simplified to their common configuration types, creating now a word of a regular language. Furthermore, the control unit of any Turing Machine is a finite automaton. Both these facts enable the Pumping Lemma in the observing Turing Machine to be usable. In compliance with the Pumping Lemma, we know that certain common configuration types must be periodically repeated in the case of the infinite length of their regular language. This fact enables us to decide that the observed computing process has entered into an infinite cycle. Considerations of the real sense of the Gibbs Paradox are used to illustrate the idea of the term &apos;step-aside&apos; which is our main methodological tool for looking for the infinite cycle in a Turing computing process and which enables us to avoid the commonly used attempts to solve the Halting Problem.

Název v anglickém jazyce

Information Thermodynamics and Halting Problem

Popis výsledku anglicky

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 &apos;observing&apos; Turing Machine, is, at any given moment, the exact copy of the computing process running in the observing machine itself . In this way an infinite cycle is created shielding what is to be possibly discovered, the possible infinite cycle in the observed computing process. By this type of our consideration and in the thermodynamic sense the equilibrium status of a certain thermodynamic system is described or, even created. This is a thermodynamic image of the Cantor diagonal method used for seeking a possible infinite cycle and which, as such, has the property of the Perpetuum Mobile, the structure of which is recognizable and therefore we can avoid it. Thus we can show that it is possible to recognize the infinite cycle as a certain original equilibrium, but with a &apos;step-aside&apos; or a time delay in evaluating the trace of the observed computing process. The trace is a record of the sequence of configurations of the observed Turing machine. These configurations can be simplified to their common configuration types, creating now a word of a regular language. Furthermore, the control unit of any Turing Machine is a finite automaton. Both these facts enable the Pumping Lemma in the observing Turing Machine to be usable. In compliance with the Pumping Lemma, we know that certain common configuration types must be periodically repeated in the case of the infinite length of their regular language. This fact enables us to decide that the observed computing process has entered into an infinite cycle. Considerations of the real sense of the Gibbs Paradox are used to illustrate the idea of the term &apos;step-aside&apos; which is our main methodological tool for looking for the infinite cycle in a Turing computing process and which enables us to avoid the commonly used attempts to solve the Halting Problem.

Druh

C - Kapitola v odborné knize

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název knihy nebo sborníku

Recent Advances in Thermo and Fluid Dynamics

ISBN

978-953-51-2239-5

Počet stran výsledku

46

Strana od-do

127-172

Počet stran knihy

331

Název nakladatele

InTech

Místo vydání

Rijeka

Kód UT WoS kapitoly

—