Information Thermodynamics and Halting Problem

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, at any given moment, the exact copy of the computing process running in the observing machine itself (the Cantor diagonal argument). 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 ’step-aside’ or a time delay in evaluating the trace of the observed computing process.

1. Introduction

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 machine itself (the Cantor diagonal argument in the Minski’s proof [18]). By this way the Auto-Reference or an infinite cycle in computing sense or the Self-Observation in information sense or an analogue of the stationary (equilibrium) state in thermodynamic sense is created, shielding now what is to be possibly discovered - the infinite cycle in the observed computing process - also for its normal input. This shield is the real result of the Cantor diagonal argument which has been used for solving the Halting Problem, but on the contrary, creates it [18]. This shield is, also, a certain image of the sought possible infinite cycle. This shield could be, in the thermodynamic point of view, ceased or ended whether the performance of the Perpetuum Mobile functionality was possible, which is not (when, e.g., the equation $$x=x+1$$ would be solvable) or by an external activity or approach.

This situation is recognizable and as such is decidable and solvable in all cases of its realizations by a certain ’step-aside’. For this, we use the previously studied [5, 6, 9, 11] congruence between a cyclical thermodynamic process represented by the Carnot Cycle and a repeatable information transfer represented by the Shannon Transfer Chain but we enrich this effort now by their another congruence with the computing process running in the Turing Machine. Considerations of Gibbs Paradox [7, 8, 11] are used to illustrate the main idea of the term ’step-aside’ which is our main methodological tool for looking for an infinite cycle in a Turing computing process and which enables us to avoid the traditional attempts of solving the Halting Problem. The gap in their formulations is due to that fact that they assume that the computing process observes itself by following itself in the same ’time-click’ of its activity. For this case the claim of the unsolvability of such a situation is, of course, valid. But with a time delay or the ’step-aside’ [or a memory (a storage)] considered it works with ’another’ data and ’is able to see’ on its own previous activity as the ’normal’ input data. The idea of the ’step-aside’ is based just on the result giving the solution to Gibbs Paradox and its information meaning [7, 8, 11, 12, 14], and enables us to be in compliance with the II. Principle of Thermodynamics during such a process.

Thus, we show that it is possible to recognize the infinite cycle, but with the time delay or a staging (instead of the time delay the staging is usable, lastng a longer time interval in each of its repetition) in evaluating the trace of the observed computing process. The trace is a message or a record, both about the input data and about the structure of the computing process being observed (the listing, the cross-references and the memory dump in the language of programmers). In this phase the observing Turing Machine (we ourselves) is raising the question: "Is there an infinite cycle?" Following the trace the observing machine gains the answer. In our case, the trace is a recorded sequence of configurations of the observed Turing Machine. These configurations can be simplified to their general configuration types which create now a word of a regular language [12, 14]. 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 used. In compliance with the Pumping Lemma, we know (the observing Turing Machine knows) that certain general configuration types must be periodically repeated in the case of the infinite length of their regular language. This fact enables us (the observing Turing Machine) to decide that the observed computing process has entered into an infinite cycle. This event is performed in a finite time and is, by this way, recognizable in the finite time, too. When the described method is used it becomes an instance of observation. By application to ’itself’ it becomes a higher instance of observation, now observing the trace of its previous instances. Thus the method of staging of the observed process will be used again. This method is applicable to all computing processes and as such it represents a contribution to the dead lock indication problem.

This sequence of ideas differs from the Cantor diagonal argument. Mainly it is achieved by the physical, especially by the thermodynamic and information (structure) type of our consideration respecting the II. Principle of Thermodynamics as the very principal root for methodological approaches of all types, both excluding and also enriching the mere empty logic.

2. Notion of Auto-Reference

Paradoxical claims (paradoxes, noetical paradoxes, contradictions, antinomia) have two parts - both parts are true, but the truth of one part denies the truth of the second part.

They can arise by not respecting the metalanguage (semantic) level - which is the higher level of our thinking about problems and the language (syntactic) level - which is the lower level of formulations of our ’higher’ thoughts. Also they arise by not respecting a double-level organization and description of measuring - by not respecting the need of a ’step-aside’ of the observer from the observed. And also they arise by not respecting various time clicks in time sequences. As for the latter case they are in a contradiction with the causality principle. The common feature for all these cases is the Auto-Reference construction which itself, solved by itself, always states the requirement for ceasing the II. Principle of Thermodynamics and all its equivalents [8-14].

Let us us introduce the Russel’s criterion for removing paradoxes

B. Russel, L. Whitehead, Principia Mathematica, 1910, 1912, 1913 and 1927.

: Within the flow of our thinking and speech we need and must distinguish between two levels of our thinking and expressing in order not to fall in a paradoxical claim by mutual mixing and changing them.

These levels are the higher one, the metalanguage (semantic) level and the lower one, the language (syntactic) level. Being aware of the existence of these two levels we prevent ourselves from their mutual mixing and changing, we prevent ourselves from application our metalanguage claims on themselves but now on the language level or vice versa.

We must be aware that our claims about properties of considered objects are created on the higher level, rather richer both semantically and syntactically than the lower one on which we really express ourselves about these objects. The words and meanings of this lower (and ’narrower’) level are common to both of them. Our speech is formulated and performed on the lower level describing here our ’higher’ thoughts and on which the objects themselves have been described, defined yet too, of course from the higher level, but with the necessary (lower) limitations. (As such they are thought over on the higher level.) From this point of view we understand the various meanings (levels) of the same words. Then any mutual mixing and changing the metalanguage and language level or the autotereference (paradox, noetical paradox, contradiction, antinomium) is excluded.

2.1. Auto-Reference in Information Transfer, Self-Observation

In any information transfer channel $$K$$ the channel equation

$$H\left(X\right)-H\left(X|Y\right)=H\left(Y\right)-H\left(Y|X\right)$$E1

it is valid [23]. This equation describes the mutual relations among information entropies [(average) information amounts] in the channel $$K$$.

The quantities $$H(X)$$, $$H(Y)$$, $$H(X|Y)$$ and $$H(Y|X)$$ are the input, the output, the loss and the noise entropy.

The difference $$H(X)-H(X|Y)$$ or the difference $$H(Y)-H(Y|X)$$ defines the transinformation $$T(X;Y)$$ or the transinformation $$T(Y;X)$$ respectively,

$$H\left(X\right)-H\left(X|Y\right)\triangleq T\left(X;Y\right)\mathrm{<mi>\; </mi><mi>\; </mi><mi>\; </mi><mo>=</mo><mi>\; </mi><mi>\; </mi><mi>\; </mi>}T\left(Y;X\right)\triangleq H\left(Y\right)-H\left(Y|X\right)$$E2

When the channel $$K$$ transfers the information (entropy) $$H(X)$$, but now just at

the value of the entropy $$H(X|Y)$$, $$H(X)=H(X|Y)$$, then, necessarily, must be valid

$$T\left(X;Y\right)\mathrm{<mo>=</mo>0<mi>\; </mi><mi>\; </mi><mi>\; </mi>}\left[=H\left(Y\right)-H\left(Y|X\right)\right]$$E3

• For $$H(Y|X)=0$$, we have $$T(X;Y)=H(Y)=0$$.

• For $$H(Y|X)\ne 0$$ we have $$H(Y)=H(Y|X)\ne 0$$

In both these two cases the channel $$K$$ operates as the interrupted (with the absolute noise) and the output $$H(Y)$$ is without any relation to the input $$H(X)$$ and, also, it doesn’t relate to the structure of $$K$$. This structure is expressed by the value of the quantity $$H(X|Y)$$. We assume, for simplicity, that $$H(Y|X)=0$$.

From the (1)-(3) follows that the channel $$K$$ can’t transfer (within the same step $$p$$ of its transfer process) such an information which describes its inner structure and, thus, it can’t transfer - observe (copy, measure) itself. It it is valid both for the concrete information value and for the average information value, as well.

Any channel $$K$$ can’t transfer its own states considered as the input messages (within the same steps $$p$$). Such an attempt is the information analogy for the Auto-Reference known from Logics and Computing Theory. Thus a certain ’step-aside’ leading to a nonzero tranfer output, $$H(Y)=H(X)-H(X|Y)>0$$, is needed.

2.2. Auto-Reference and Thermodynamic Stationarity

The transfer process running in an information transfer channel $$K$$ is possible to be comprehended (modeled or, even, constructed) as the direct Carnot Cycle $$O$$ [6, 8]. The relation $$O\cong K$$ is postulated. Further, we can imagine its observing method, equivalent to its ’mirror’ $$O^{″}\cong K^{″}$$. This mirror $$O^{″}$$ is, at this case, the direct Carnot Cycle $$O$$ as for its structure, but functioning in the indirect, reverse mode [6, 8].

Let us connect them together to a combined heat cycle $$O{O}^{″}$$ in such a way that the mirror (the reverse cycle $$O^{″}$$) is gaining the message about the structure of the direct cycle $$O$$. This message is (carrying) the information $$H(X|Y)$$ about the structure of the transformation (transfer) process $$(O\cong K)$$ being ’observed’. The mirror $$O^{″}\cong K^{″}$$ is gaining this information $$H(X|Y)$$ on its noise ’input’ $$H({Y^{\prime }}^{\prime }|{X^{\prime }}^{\prime })$$ [while $$H({X^{\prime }}^{\prime })=H(Y)$$ is its input entropy].

The quantities $$\mathrm{\Delta }{Q}_W$$, $$\mathrm{\Delta }A$$ and $$\mathrm{\Delta }{Q}_0$$ or the quantities $$\mathrm{\Delta }{{Q^{\prime }}^{\prime }}_W$$, $$\mathrm{\Delta }{A^{\prime }}^{\prime }$$ and $$\mathrm{\Delta }{{Q^{\prime }}^{\prime }}_0$$ respectively, define the information entropies of the information transfer realized (thermodynamically) by the direct Carnot Cycle $$O$$ or by the reverse Carnot Cycle $$O^{″}$$ (the mirror) respectively (the combined cycle $$O{O}^{″}$$ is created),

$$\begin{array}{l}H\left(X\right)=\frac{\mathrm{\Delta }{Q}_W}{\text{k}{T}_W}\mathrm{,}\mathrm{resp}\mathrm{.}H\left({Y^{\prime }}^{\prime }\right)=\frac{\mathrm{\Delta }{{Q^{\prime }}^{\prime }}_W}{\text{k}{{T^{\prime }}^{\prime }}_W}\\ H\left(Y\right)=\frac{\mathrm{\Delta }A}{\text{k}{T}_W}\mathrm{,}\mathrm{resp}\mathrm{.}H\left({X^{\prime }}^{\prime }\right)=\frac{\mathrm{\Delta }{A^{\prime }}^{\prime }}{\text{k}{{T^{\prime }}^{\prime }}_W}\\ H\left(X|Y\right)=\frac{\mathrm{\Delta }{Q}_0}{\text{k}{T}_W}\mathrm{,}\mathrm{resp}\mathrm{.}H\left({Y^{\prime }}^{\prime }|{X^{\prime }}^{\prime }\right)=\frac{\mathrm{\Delta }{{Q^{\prime }}^{\prime }}_0}{\text{k}{{T^{\prime }}^{\prime }}_W}\end{array}$$E4

Our aim is to gain the nonzero output mechanical work $$\mathrm{\Delta }{A}^{*}$$ of the combined heat cycle $$O{O}^{″}$$, $$\mathrm{\Delta }{A}^{*}>0$$. We want to gain nonzero information $$H^{*}(Y^{*})=\mathrm{\Delta }{A}^{*}/\text{k}{T}_W>0$$.

To achieve this aim, for the efficiencies $${\eta }_{max}$$ and $${{\eta }^{″}}_{max}$$ of the both connected cycles $$O$$ and $$O^{″}$$ (with the working temperatures $$T_W={{T^{\prime }}^{\prime }}_W$$ and $$T_0={{T^{\prime }}^{\prime }}_0$$, $$T_W\ge T_0>0$$), it must be valid that $${\eta }_{max}>{{\eta }^{″}}_{max}$$ ; we want the validity of the relation

We follow the proof of physical and thus logical impossibility of the construction and functionality of the Perpetuum Mobile of the II. and, equivalently [8], of the I. type.

$${\mathrm{\Delta }}^{*}A=\mathrm{\Delta }A-\mathrm{\Delta }{A^{\prime }}^{\prime }\mathrm{<mo>></mo>0<mi>\; </mi><mi>\; </mi>}\left[\mathrm{\Delta }{A^{\prime }}^{\prime }=\mathrm{\Delta }{{Q^{\prime }}^{\prime }}_W-\mathrm{\Delta }{{Q^{\prime }}^{\prime }}_0\right]$$E5

When $$\mathrm{\Delta }{Q}_0=\mathrm{\Delta }{{Q^{\prime }}^{\prime }}_0$$ should be valid, then must be that $$\mathrm{\Delta }{{Q^{\prime }}^{\prime }}_W<\mathrm{\Delta }{Q}_W\mathrm{<mi>\; </mi><mi>\; </mi><mo\; stretchy="false">[</mo>}\Leftarrow ({\eta }_{max}>{{\eta }^{″}}_{max})]$$ and thus it should be valid that

$$\begin{array}{l}\mathrm{\Delta }{A}^{*}=\mathrm{\Delta }{Q}_W\cdot {\eta }_{max}-\mathrm{\Delta }{Q^{″}}_W\cdot {{\eta }^{″}}_{max}>0\mathrm{but}\\ \mathrm{\Delta }{Q}_W\cdot {\eta }_{max}-\mathrm{\Delta }{Q^{″}}_W\cdot {{\eta }^{″}}_{max}=\mathrm{\Delta }{Q}_0-\mathrm{\Delta }{Q^{″}}_0=0\end{array}$$E6

Thus the output work $$\mathrm{\Delta }{A}^{*}>0$$ should be genarated without any lost heat and by the direct change of the whole heat $$\mathrm{\Delta }{Q}_W-\mathrm{\Delta }{Q^{″}}_W$$ but within the cycle $$O{O}^{″}$$. For $${\eta }_{max}<{\eta }_{max}$$ the same heat $$\mathrm{\Delta }{Q}_W-\mathrm{\Delta }{{Q^{\prime }}^{\prime }}_W$$ should be pumped from the cooler with the temperature $$T_0$$ to the heater with the temperature $$T_W$$ directly, without any compensation by a mechanical work. We see that $$\mathrm{\Delta }{A}^{*}=0$$ is the reality.

Our combined machine $$O{O}^{″}$$ should be the II. Perpetuum Mobile in both two cases. Thus $${\eta }_{max}={{\eta }^{″}}_{max}$$ must be valid (the heater with the temperature $$T_W$$ and the cooler with the temperature $$T_0$$ are common) that

$${\eta }_{max}={{\eta }^{″}}_{max}<1\mathrm{and}\mathrm{then}\mathrm{\Delta }{Q}_W=\mathrm{\Delta }{Q^{″}}_W$$E7

We must be aware that for $${\eta }_{max}={{\eta }^{″}}_{max}<1$$ the whole information entropy of the environment in which our (reversible) combined cycle $$O{O}^{″}$$ is running changes on one hand by the value

$$H(X)\cdot {\eta }_{max}=\frac{\mathrm{\Delta }{Q}_W}{\text{k}{T}_W}\cdot \left(1-\beta \right)\mathrm{<mo>></mo>0,<mi>\; </mi><mi>\; </mi>}\beta =1-{\eta }_{max}=\frac{T_0}{T_W}$$E8

and on the other hand it is also changed by the value $$-H(X)\cdot {\eta }_{max}=-\frac{\mathrm{\Delta }{Q}_W}{\text{k}{T}_W}\cdot \left(1-\beta \right)$$

Thus it must be changed by the zero value

$$H^{*}(Y^{*})=\frac{\mathrm{\Delta }{A}^{*}}{\text{k}{T}_W}=H(X)\cdot {\eta }_{max}-H(Y^{″})\cdot {{\eta }^{″}}_{max}=H(X)\cdot \left({\eta }_{max}-{\eta }_{max}\right)\mathrm{<mo>=</mo>0<mi>\; </mi><mi>\; </mi>}$$E9

The whole combined machine, or the thermodynamic system with the cycle $$O{O}^{″}$$ is, when the cycle $$O{O}^{″}$$ is seen, as a whole, in the thermodynamic equilibrium. (It can be seen as an unit, analogous to an interruptable operation in computing.)

Figure 1.

Stationarity of the double cycle $$O{O}^{″}$$

Thus, the observation of the observed process $$O$$ by the observing reverse process $$O^{″}$$ with the same structure (by itself), or the Self-Observation, is impossible in a physical sense, and, consequently, in a logical sense, too (see the Auto-Reference in computing).

Nevertheless, the construction of the Auto-Reference is describable and, as such, is recognizable, decidable just as a construction sui generis. It leads, necessarily, to the requirement of the II. Perpetuum Mobile functionality when the requirements (5) and (6) are sustained.

(Note, that the Carnot Machine itself is, by its definition, a construction of the infinite cycle of the states of its working medium and as such is identifiable and recognizable.)

2.3. Gibbs Paradox and Auto-Reference in Observation and Information Transfer

Only just by a (thought) ’dividing’ of an equilibrium system $$A$$ by diaphragms [20], without any influence on its thermodynamic (macroscopic) properties, a non-zero difference of its entropy, before and after its ’dividing’, is evidenced.

Let us consider a thermodynamic system $$A$$ in volume $$V$$ and with $$n$$ matter units of ideal gas in the thermodynamic equilibrium. The state equation of $$A$$ is $$pV=nR\mathrm{\Theta }$$. For an elementary change of the internal energy $$U$$ of $$A$$ we have $$\text{d}U=n{c}_v\text{d}\mathrm{\Theta }$$.

From the state equation of $$A$$, and from the general law of energy conservation [for a (substitute) reversible exchange of heat $$\delta q$$ between the system and its environment] we formulate the I. Principle of Thermodynamics, $$\delta q=\text{d}U+p\text{d}V$$

From this principle, and from Clausius equation $$\mathrm{\Delta }S\stackrel{\text{Def}}{=}\frac{\mathrm{\Delta }q}{\mathrm{\Theta }}\mathrm{,}\mathrm{\Delta }q=c_v\mathrm{\Delta }\mathrm{\Theta }+\frac{R\mathrm{\Theta }\mathrm{\Delta }V}{V}\mathrm{,}\mathrm{\Theta }>0$$, follows that

$$S=n{\displaystyle \int }\left(c_v\frac{\text{d}\mathrm{\Theta }}{\mathrm{\Theta }}+R\frac{\text{d}V}{V}\right)=n\left(c_v\ln \mathrm{\Theta }+R\ln V\right)+S_0(n)=\sigma \left(\mathrm{\Theta }\mathrm{,}V\right)+S_0(n\mathrm{<mo\; stretchy="false">)</mo><mi>\; </mi><mi>\; </mi>}$$E10

Let us ’divide’ the equilibrial system $$A$$ in a volume $$V$$ and at a temperature $$\mathrm{\Theta }$$, or, better said, the whole volume $$V$$ (or, its whole state space) occupiable, and just occupied now by all its constituents (particles, matter units), with diaphragms (thin infinitely, or, ’thought’ only), not affecting thermodynamic properties of $$A$$ supposingly, to $$m$$ parts $$A_i$$, $$i\in \mathrm{<mo>\{</mo>1,<mi>\; </mi>...,<mi>\; </mi>}m\}$$, $$m\ge 1$$ with volumes $$V_i$$ with matter units $$n_i$$. Evidently $$n={\displaystyle {\sum }_{i=1}^m}{n}_i$$ and $$V={\displaystyle {\sum }_{i=1}^m}{V}_i$$.

Let now $$S_0(n)=0$$ and $$S_{0i}(n_i)=0$$ for all $$i$$. For the entropies $$S_i$$ of $$A_i$$ considered individually, and for the change $$\mathrm{\Delta }S$$, when volumes $$V\mathrm{,}{V}_i$$ are expressed from the state equations, and for $$p=p_i$$, $$\mathrm{\Theta }={\mathrm{\Theta }}_i$$ it will be gained that $${\sigma }_{[i]}=R{n}_{[i]}\ln n_{[i]}$$. Then, for $$S_i={\sigma }_i=n_i\left(c_v\ln \mathrm{\Theta }+R\ln V_i\right)$$ is valid, we have that

$$\begin{array}{l}{\displaystyle \sum _{i=1}^m}{S}_i={\displaystyle \sum _{i=1}^m}{\sigma }_i=n{c}_v\ln \mathrm{\Theta }+R\ln \left({\displaystyle \prod _{i=1}^m}{V}_i{}^{n_i}\right)\mathrm{,}\\ \mathrm{\Delta }S=S-{\displaystyle \sum _{i=1}^m}{S}_i=\sigma -{\displaystyle \sum _{i=1}^m}{\sigma }_i=\mathrm{\Delta }\sigma =R\ln \frac{V^n}{{\displaystyle \prod _{i=1}^m}{V}_i{}^{n_i}}=-nR{\displaystyle \sum _{i=1}^m}\frac{n_i}{n}\ln \frac{n_i}{n}>0\end{array}$$E11

Let us denote the last sum as $$B$$ further on, $$B<0$$. The quantity $$-B$$ expressed in (11) is information entropy of a source of messages with an alphabet $$\left[n_1\mathrm{,}{n}_2\mathrm{,<mi>\; </mi>...<mi>\; </mi>,}{n}_m\right]$$ and probability distribution $${\left[n_i/n\right]}_{i=1}^m$$. Such a division of the system to $$m$$ parts defines an information source with the information entropy with its maximum $$\ln m$$.

The result (11), $$\mathrm{\Delta }S=-nRB$$, is a paradox, a contradiction with our presumption of not influencing a thermodynamic state of $$A$$ by diaphragms, and, leads to that result that the heat entropy $$S$$ (of a system in equilibrium) is not an extensive quantity. But, by the definition of the differential $$\text{d}S$$, this is not true.

Due to this contradiction we must consider a non-zero integrating constants $$S_0(n)$$, $$S_{0i}(n_i)$$, in such a way, that the equation $$\mathrm{\Delta }S=(\sigma +S_0)-{\displaystyle {\sum }_{i=1}^m}({\sigma }_i+S_{0i})=0$$ is solvable for the system $$A$$ and all its parts $$A_i$$ by solutions $$S_{0[i]}(n_{[i]})=-n_{[i]}R\ln \left(n_{[i]}/{\gamma }_{[i]}\right)$$.

Then $$S_{[i]}\triangleq S_{[i]}^{Claus}$$, and we write and derive that

$$S^{Claus}={\displaystyle \sum _{i=1}^m}{S}_i^{Claus}={\displaystyle \sum _{i=1}^m}{n}_{i}R\ln {\gamma }_i=nR\ln \gamma \Rightarrow \gamma ={\gamma }_i\mathrm{<mo>;</mo><mi>\; </mi><mi>\; </mi>}\mathrm{\Delta }S=0.$$E12

Now let us observe an equilibrium, $$S^{\ast }=S^{Claus}=S^{Boltz}=-kN{B}^{\ast }=-kN\ln N$$.

Let, in compliance with the solution of Gibbs Paradox, the integration constant $$S_0$$ be the (change of) entropy $$\mathrm{\Delta }S$$ which is added to the entropy $$\sigma$$ to figure out the measured entropy $$S^{Claus}$$ of the equilibrium state of the system $$A$$ (the final state of Gay-Lussac experiment) at a temperature $${\mathrm{\Theta }}_{}$$. We have shown that without such correction, the less entropy $$\sigma$$ is evidenced, $$\sigma =S^{Claus}-\mathrm{\Delta }S\mathrm{,}\mathrm{\Delta }S=S_0$$.

Following the previuos definitions and results we have

$$\begin{array}{l}\mathrm{\Delta }S=\frac{\mathrm{\Delta }{Q}_0}{\mathrm{\Theta }}=-nR\ln \frac{n}{\gamma }\mathrm{,}\\ \ln \gamma =\frac{\mathrm{\Delta }S}{kn{N}_A}+\ln n=\frac{\mathrm{\Delta }S}{kN}+\ln N-\ln N_A\mathrm{,}\gamma =N\Rightarrow \frac{\mathrm{\Delta }S}{kN}=\ln N_A\mathrm{.}\end{array}$$E13

By the entropy $$\mathrm{\Delta }S$$ the ’lost’ heat $$\mathrm{\Delta }{Q}_0$$ (at the temperature $${\mathrm{\Theta }}_{}$$) is defined.

Thus, our observation can be understood as an information transfer $$T$$ in an information channel $$K$$ with entropies $$H(X)$$, $$H(Y)$$, $$H(X|Y)$$ and $$H(Y|X)$$ in (4) but now bound physically; we have these information entropies per one particle of the observed system $$A$$ :

$$\begin{array}{l}inputH(X)\stackrel{\text{Def}}{=}\frac{S\ast }{kN}=\ln \gamma =-B\ast =\ln N=-rB(r)\hfill \\ outputH(Y)\stackrel{\text{Def}}{=}\frac{\sigma }{kN}\triangleq -B^{Gibbs}=-B^{Boltz}=-B(r)\mathrm{,}\hfill \\ lossH(X|Y)\stackrel{\text{Def}}{=}\frac{S_0}{kN}\mathrm{,}\hfill \\ noiseH(Y|X)\stackrel{\text{Def}}{=}0\mathrm{for}\mathrm{the}\mathrm{simplicity};\hfill \\ H(X|Y)=-rB(r)-\left[-B(r)\right]=-B(r)\cdot (r-1)=\left(-B\ast \right)\cdot \frac{r-1}{r}\mathrm{,}r\ge \mathrm{1<mo>;</mo><mi>\; </mi><mi>\; </mi>}\frac{1}{r}={\eta }_{max}\mathrm{.}\hfill \end{array}$$E14

For a number $$m$$ of cells of our railings in the volume $$V$$ with $$A$$, $$m\le N$$ or for the accuracy $$r$$ of this description of the ’inner structure’ of $$A$$ (a thought structure of $$V$$ with $$A$$) and for the number $$q$$ of diaphragms creating our railings of cells and constructed in such a way that $$q\in \mathrm{<mo><</mo>1,<mi>\; </mi>}m-1>$$, we have that $$r=(N-1)/q$$.

Our observation of the equilibrium system $$A$$, including the mathematical correction for Gibbs Paradox, is then describable by the Shannon transfer scheme $$[X\mathrm{,}K\mathrm{,}Y]$$ where

$$H(X)=\frac{S^{Claus}}{kN}\mathrm{,}H(X|Y)=\frac{S_0}{kN}\mathrm{,}H(Y)=\frac{S^{Claus}}{kN}\mathrm{,}H(Y|X)=\frac{\mathrm{\Delta }S}{kN}\mathrm{.}$$E15

(However, a real observation process described in (15), equivalent to that one with $$r=1$$, is impossible [6].)

We conclude by that, the diminishing of the measured entropy value about $$\mathrm{\Delta }S$$ against $$S\ast$$ awaited, evidenced by Gibbs Paradox, does not originate in a watched system itself. Understood this way, it is a contradiction of a gnozeologic character based on not respecting real properties of any observation [6]. And, this means the following.

The minimal accuracy of our description of the watched system $$A$$ should be for $$r=\infty$$. In this case we should place $$q=0$$ diaphragms, no railings is laid, $$m=1$$, $$q=0$$. ’We think nothing’ about the ’inner structure’ of the system $$A$$, for in this case we are not outside of it (for the ’structure’ measured - considered is ’created’ by 0 diaphragms ’laid down’ just from the outside). Thus we define an output information source $$Y$$, which is bound physically, and for which its (bound) information entropy is $$H(Y)=-B^{Gibbs}=0$$. Then, the result of such ’observation’ is 0, and the loss information entropy is

$$H(X|Y)=\frac{S*}{kN}=\ln N=H(X)\mathrm{.}$$BB1

If we consider $$m>1$$ as the number of ’windows’ being laid down over the measured (observed) system $$A$$ from the outside, but now $$m=1$$ and then $$q=0$$, we resign the possibility of saying about the system $$A$$ anything else than that it exists. The whole system $$A$$ is now ’viewed’ in the just one ’window’ but now created by the volume $$V$$, the system $$A$$ occupies, itself. This only one observation ’window’ is ’pressed’ to us by the system $$A$$ itself and, by this way, ’we ourselves are identical’ with it, ’we ourselves are’ the system $$A$$. We ’can move’ within the volume $$V$$, but ’undivided’ this time, and thus our measuring could be ’organized’ now by the mediation of this only one window, but not laid down from the outside (by us). We are inside of this system (of the volume $$V$$) and our measuring is organized with the parameter $$r=\infty$$. We say that we are identical with the system for we have now no ’step-aside’ from it $$[H(Y)=H(X)-H(X|Y)=0]$$. This is the reason why we do not see it (from the outside) and, what we can think about it is nothing. In such a sense that we can’t ’lay down’ the diaphragms over the system ($$q\ne 0$$ is needed) and create on it our ’windows’ $$(m>1)$$. Because we do not rule our measuring of the system $$A$$ we do not ’divide’ it by our, just from the outside laid, diaphragms (now $$q=0$$) and, for this, we are not able to organize its measuring with the parameter $$r<\infty$$. ’We ourselves are’ the system $$A$$ and for this we can’t, from the outside, see us, which means we can’t see the system. (Or we can evidence its or our certain existence in this window.) The Auto-Reference is not possible; the measuring of the system $$A$$ (from the outside !) is intended to be organized in the inside (!) of the system $$A$$ itself.

Our eye cannot see itself by itself only and, even more, it cannot see inside itself by itself only.

Our measuring also represents an observation of a certain phenomenon with the degenerated probability distribution $${\left[n_i/n\right]}_{i=1}^1$$. The information amounts $$i(X)$$ and $$H(X)$$ of this phenomenon are equal to 0 and, due to this, our measuring organized by the measuring method with the parameter $$m=1$$ or $$r=\infty$$ respectively will end with the result $$H(Y)=0$$ $$\left[H(Y)={\eta }_{max}\cdot H(X\mathrm{<mo\; stretchy="false">)</mo><mo>;</mo><mi>\; </mi><mi>\; </mi>}H(X)=\mathrm{0,}{\eta }_{max}=1/\infty \right]$$.

For this all we need a certain ’step-aside’ from the system $$A$$ expressed by the value $$r<\infty$$, but, nevertheless with respecting properties of this ’step-aside’, we do not fall into Gibbs Paradox [even when our railngs of diafragmas in the mode given $$r\in (\mathrm{1,}\infty ⟩$$ is laid down].

The ideal ’step-aside’ is expressed by the value $$r=1$$.

The maximal accuracy of our ’description’, the accuracy of our watching of the system $$A$$, is achieved for $$r=1$$. Then $$B(r)=B*$$ and for the output, the input and the loss information entropies it is valid that

$$H(Y)=H(X)=-B\ast \mathrm{,}H(X|Y)=0$$BB2

Then we have the ideal ’step-aside’ from the system $$A$$. ’We have insight into its inside’ and we can draw a layout of measuring its state without the distortion being given by the (at least partial) transfer (energy) of its state into the organization of our measuring [in the form of the nonzero value of the information loss $$H(X|Y)$$ when $$r\in (\mathrm{1,}\infty ⟩$$.]

This ’step-aside’ enables us to set our measuring with the parameter $$q=N-\mathrm{1,}r=1$$. Now we know exactly what we measure, we know that we measure the status of the equilibrium thermodynamic system $$A$$ and, by our ’step-aside’ from it, we are able to check the precision (the organization) of the measuring method. Just this enables us to organize the measuring of the status of the system $$A$$ without nonzero information loss $$H(X|Y)$$ in the other case being generated by the method itself (for $$r\ne 1$$), see the mentioned above gnozeological defect.

[But note that something quite different is the realization of the measuring method where the information losses are inevitable yet as the result of the validity of the II. Principle of Thermodynamics (and its equivalents [8]).]

3. Information Thermodynamic Concept Removing Auto-Reference

In the Auto-Reference case, the whole combined machine $$O{O}^{″}$$ is a system in the equilibrium status. For this status we can introduce the term (quasi)stationary status in which the (infinitesimal) part of heat is circulating. Any round of this circulation is lasting the time interval $$\mathrm{\Delta }t$$ ; infinite, $$\mathrm{\Delta }t\to \infty$$, for not ideal model, or, finite, $$\mathrm{\Delta }t\mathrm{<mi>\; </mi><mo><</mo><mi>\; </mi>}\infty$$, when the ideal model is used; then the part of heat cannot be the infinitesimal. With the exception of the II. Perpetuum Mobile functionality of this combined machine, which is not possible, see (5) and (6), only the opening of the system and an external activity, a certain ’step-aside’ between the cycles $$O$$ and $$O^{″}$$, moves it away (prevent it) from this status.

Nevertheless, we sustain our wants of gaining the information (about) $$H(X|Y)$$ about the structure of the observed $$O$$ (the transfer channel $$K$$), we want the nonzero value $$\mathrm{\Delta }{A}^{*}$$, the nonzero information $$H^{*}(Y^{*})=\mathrm{\Delta }{A}^{*}/\text{k}{T}_W>0$$.

Then, necessarily, the mirror, the reverse Carnot Cycle $$O^{″}$$ (the transfer channel $$K^{″}$$) is to be constructed with that ’step-aside’ (excluding that stationarity) from the observed $$O\cong K$$. Now we mean that the ’step-aside’ of the observing process $$O$$ from the observed process $$O^{″}$$ is realized by the difference $$T_W-{{T^{\prime }}^{\prime }}_W>0$$. Now, within this thermodynamic point of view, it is valid that $$\mathrm{\Delta }{A}^{″}<\mathrm{\Delta }{A}^{″}$$ for $$T_0={{T^{\prime }}^{\prime }}_0$$, $${T^{″}}_W\triangleq T^{*}{}_0$$

$$\mathrm{\Delta }{A}^{″}=\mathrm{\Delta }{Q^{″}}_W\cdot \left(1-\frac{T_0}{{T^{″}}_W}\right)=\mathrm{\Delta }{Q}_W\cdot \frac{{T^{″}}_W}{T_W}\cdot \left(1-\frac{T_0}{{T^{″}}_W}\right)$$E16

Then, for the whole information amount $$\mathrm{\Delta }{A}^{*}/\text{k}{T}_W$$ of our combined cycle it is valid that

$$\frac{\mathrm{\Delta }{A}^{*}}{\text{k}{T}_W}=H(Y^{″})-H(Y^{″})\cdot {\beta }^{*}=H(Y^{″})\cdot \left(1-\frac{T_0{}^{*}}{T_W}\right)=H(Y^{″})\cdot \left[1-\frac{H(X|Y)}{H(X^{″}|Y^{″})}\right]$$E17

The structure $$H(X|Y)$$ of the observed transfer (channel, process) $$O\cong K$$ is measurable with the ’step-aside’ only, created now by different temperatures $$(T_W>{T^{″}}_W)$$. The result is

$$\frac{\mathrm{\Delta }{A}^{*}}{\text{k}{T}_W}\mathrm{<mo>></mo>0,<mi>\; </mi><mi>\; </mi>}\left[\frac{\mathrm{\Delta }{A}^{*}}{\text{k}{T}_W}\cong f\left[H(X|Y)\right]>0\right]$$E18

Following (5), (6) and (9) the Auto-Reference arises just when

$$T_W={T^{″}}_W\left[\Rightarrow H(Y)=0\right]$$E19

Now we will describe, in the information thermodynamic way, the problem of a Self-Observation or the Auto-Reference problem and will draw a method of its ceasing.

For we want to have the information $$H(X|Y)$$ describing the structure of the transfer process $$O\cong T$$ which we observe we need gain a nonzero value (difference) $$\mathrm{\Delta }{A}^{*}$$ and, consequently, a nonzero information $$H^{*}(Y^{*})$$,

$$H^{*}(Y^{*})=\frac{\mathrm{\Delta }{A}^{*}}{\text{k}{T}_W}>0$$E20

Then we need a ’mirror’, the reverse Carnot Cycle $$O^{″}\cong T^{″}$$ (or the relevant transfer channel $$K^{″}$$) would be constructed in such a way that the mentioned ’step-aside’ from the observed transfer channel $$K$$ was respected. [It is the ’step-aside’ of the observing process ($$O^{″}$$, $$T^{″}$$) from the observed process ($$O$$, $$T$$); also we can consider a computing process $$\overrightarrow{\kappa }$$ and its description - the program $$\overrightarrow{\eta }$$, and its observation, see later].

Now the required ’step-aside’ is realized by the temperature difference $$T_W-{{T^{\prime }}^{\prime }}_W>0$$. Thus now we consider, within the frame of our thermodynamic approach, that $$\mathrm{\Delta }{A}^{″}<\mathrm{\Delta }{A}^{″}$$ for $$T_0={{T^{\prime }}^{\prime }}_0$$ and then, under the condition $$\mathrm{\Delta }{Q}_0=\mathrm{\Delta }{Q^{″}}_0$$, it will be valid for the cycles $$O$$, $$O^{″}$$ and $$O{O}^{″}$$ that

$$\begin{array}{l}\mathrm{\Delta }{Q^{″}}_W=\mathrm{\Delta }{A}^{″}+\mathrm{\Delta }{Q^{″}}_0\\ =\mathrm{\Delta }{Q^{″}}_W\cdot {{\eta }^{″}}_{max}+\mathrm{\Delta }{Q}_W\cdot \left(1-{\eta }_{max}\right)\\ =\mathrm{\Delta }{Q^{″}}_W\cdot {{\eta }^{″}}_{max}+\mathrm{\Delta }{Q}_W-\mathrm{\Delta }{Q}_W\cdot {\eta }_{max}\end{array}$$E21

but also it is valid that

$$\begin{array}{l}\mathrm{\Delta }{Q}_W=\mathrm{\Delta }{Q^{″}}_W\cdot {{\eta }^{″}}_{max}+\mathrm{\Delta }{Q^{″}}_W\cdot \left(1-{{\eta }^{″}}_{max}\right)\\ =\mathrm{\Delta }{Q^{″}}_W\cdot {{\eta }^{″}}_{max}+\mathrm{\Delta }{Q^{″}}_W-\mathrm{\Delta }{Q^{″}}_W\cdot {{\eta }^{″}}_{max}\end{array}$$E22

From the proposition $$\mathrm{\Delta }{Q}_0=\mathrm{\Delta }{Q^{″}}_0$$ [from relations (21) and (22)] pro $$\mathrm{\Delta }{Q^{″}}_W$$ follows that

$$\mathrm{\Delta }{Q}_W\cdot \left(1-{\eta }_{max}\right)=\mathrm{\Delta }{Q^{″}}_W\cdot \left(1-{{\eta }^{″}}_{max}\right)$$E23

With the denotation $$\beta \triangleq (1-{\eta }_{max}\mathrm{<mo\; stretchy="false">)</mo>,<mi>\; </mi><mi>\; </mi>}{\beta }^{″}\triangleq (1-{{\eta }^{″}}_{max})$$ we write

$$\begin{array}{c}\mathrm{\Delta }{Q}_W\cdot \beta =\mathrm{\Delta }{Q^{″}}_W\cdot {\beta }^{″}\\ \frac{\mathrm{\Delta }{Q}_W}{\mathrm{\Delta }{Q^{″}}_W}=\frac{T_W}{{T^{″}}_W}=\frac{\frac{T_0}{{T^{″}}_W}}{\frac{T_0}{T_W}}=\frac{{\beta }^{″}}{\beta }\\ \Rightarrow \\ \mathrm{\Delta }{Q^{″}}_W=\mathrm{\Delta }{Q}_W\cdot \frac{\beta }{{\beta }^{″}}=\mathrm{\Delta }{Q}_W\cdot \frac{{T^{″}}_W}{T_W}\mathrm{,}\mathrm{\Delta }{Q^{″}}_W<\mathrm{\Delta }{Q}_W\end{array}$$E24

Within the cycles $$O$$ and $$O^{″}$$ the following relations are valid,

$$\begin{array}{l}\frac{T_W-T_0}{T_W}>\frac{{T^{″}}_W-T_0}{{{T^{\prime }}^{\prime }}_W}\mathrm{,}{T}_W>{T^{″}}_W\\ \frac{T_0}{{T^{″}}_W}>\frac{T_0}{T_W}\mathrm{a}tedy\frac{Q_0}{{Q^{″}}_W}>\frac{Q_0}{Q_W}\mathrm{,}{Q}_W>{Q^{″}}_W\\ \Rightarrow \\ \frac{H\left(Y^{″}|X^{″}\right)}{H\left(Y^{″}\right)}>\frac{H\left(X|Y\right)}{H\left(X\right)}\end{array}$$E25

Figure 2.

The concept for ceasing the Auto-Reference

By (23) and (24) for $$\mathrm{\Delta }{A}^{″}$$ it is valid in the cycle $$O^{‴}$$ that

$$\begin{array}{l}\mathrm{\Delta }{A}^{″}=\mathrm{\Delta }{Q^{″}}_W\cdot \left(1-\frac{T_0}{{T^{″}}_W}\right)=\mathrm{\Delta }{Q}_W\cdot \frac{{T^{″}}_W}{T_W}\cdot \left(1-{\frac{T_0}{T^{″}}}_W\right)=\\ =\mathrm{\Delta }{Q}_W\cdot \left(\frac{{T^{″}}_W}{T_W}-\frac{T_0}{T_W}\right)=\text{k}\cdot H(X)\cdot \left({T^{″}}_W-T_0\right)\\ =\text{k}\cdot H(X)\cdot {T^{″}}_W\left(1-\frac{T_0}{{T^{\prime }}_W}\right)=\text{k}\cdot H(X)\cdot {T^{″}}_W(1-{\beta }^{″})=\text{k}\cdot {T^{″}}_W\cdot H(Y^{″})\end{array}$$E26

and, further, for $$\mathrm{\Delta }A$$ in the cycle $$O$$ we have

$$\mathrm{\Delta }A=\text{k}\cdot H(X)\cdot T_W(1-\beta )=\text{k}\cdot H(X)\cdot T_W\left(1-\frac{T_0}{T_W}\right)$$E27

and thus, for the cycles $$O^{″}$$ and $$O$$ it is valid that

$${\frac{\mathrm{\Delta }{A}^{″}}{\text{k}{T}^{″}}}_W=H(X)\cdot \left(1-{\frac{T_0}{T^{″}}}_W\right)=H(X)\cdot (1-{\beta }^{″})=H(X)\cdot {{\eta }^{″}}_{max}$$E28

$$\frac{\mathrm{\Delta }A}{\text{k}{T}_W}=H(X)\cdot \left(1-\frac{T_0}{T_W}\right)=H(X)\cdot (1-\beta )=H(X)\cdot {\eta }_{max}$$BB3

For the whole work $$\mathrm{\Delta }{A}^{*}$$ of the combined cycle $$O{O}^{″}$$ we have

$$\mathrm{\Delta }{A}^{*}=\mathrm{\Delta }A-\mathrm{\Delta }{A}^{″}=\left[\text{k}{T}_W\cdot H(X)\cdot (1-\beta )-k{T^{″}}_W\cdot H(X)\cdot (1-\beta {\text{'}}^{″})\right]>0$$E29

Then, for the whole change of the thermodynamic entropy within the combined cycle $$O{O}^{″}$$ (measured in information units Hartley, nat, bit) and thus for the change of the whole information entropy $$H^{*}\left(Y^{*}\right)\left[\triangleq H_C\right]$$, following the relation (29), it is valid

$$\begin{array}{l}{H}^{*}(Y^{*})=\frac{\mathrm{\Delta }{A}^{*}}{\text{k}{T}_W}=H(X)\cdot \left[(1-\beta )-\frac{{T^{″}}_W}{T_W}\cdot (1-{\beta }^{\prime })\right]\\ =H(X)\cdot \left(1-\frac{T_0}{T_W}-\frac{{T^{″}}_W}{T_W}+\frac{T_0}{T_W}\right)=H(X)\cdot \left(1-\frac{{T^{″}}_W}{T_W}\right)\end{array}$$E30

It is valid, for $$\mathrm{\Delta }{A}^{*}$$ is a residuum work after the work $$\mathrm{\Delta }A$$ has been performed at the temperature $$T_W$$. Evidently, the sense of the symbol $${T^{″}}_W$$ (within the double cycle $$O{O}^{″}$$ and when $$\mathrm{\Delta }{Q}_0=\mathrm{\Delta }{Q^{″}}_0$$) is expressible by the symbol $$T_0{}^{*}$$, which is possible, for the working temperatures of the whole cycle $$O{O}^{″}$$ are $$T_W$$ and $${T^{″}}_W=T_0{}^{*}$$. The relation (30) expresses that fact that the double cycle $$O{O}^{″}$$ is the direct Carnot Cycle just with its working temperatures $$T_W>{T^{″}}_W=T_0{}^{*}$$. In the double cycle $$O{O}^{″}$$ it is valid that

$$\begin{array}{l}{\beta }^{″}=\frac{\mathrm{\Delta }{Q^{″}}_0}{\mathrm{\Delta }{Q^{″}}_W}=\frac{\frac{\mathrm{\Delta }{Q^{″}}_0}{{T^{″}}_W}}{\frac{\mathrm{\Delta }{Q^{″}}_W}{{T^{″}}_W}}=\frac{H(Y^{″}|X^{″})}{H({Y^{\prime }}^{\prime })}=\frac{T_0}{{T^{″}}_W}\mathrm{,}{T^{″}}_W=T_0{}^{*}\mathrm{,}\mathrm{cyklus}{O}^{″}\\ \beta =\frac{\mathrm{\Delta }{Q}_0}{\mathrm{\Delta }{Q}_W}=\frac{\frac{\mathrm{\Delta }{Q}_0}{T_W}}{\frac{\mathrm{\Delta }{Q}_W}{T_W}}=\frac{H(X|Y)}{H(X)}=\frac{T_0}{T_W}\mathrm{,}\mathrm{cyklus}O\\ \frac{\beta }{{\beta }^{″}}=\frac{{T^{″}}_W}{T_W}=\frac{T_0{}^{*}}{T_W}\triangleq {\beta }^{*}\end{array}$$E31

and then, by (30) a (31) is writable that

$$\frac{\mathrm{\Delta }{A}^{*}}{\text{k}{T}_W}=H(X)\cdot \left(1-{\beta }^{*}\right)=H(X)\cdot \left[1-\frac{H(X|Y)\cdot H(Y^{″})}{H(Y^{″}|X^{″})\cdot H(X)}\right]>0$$E32

It is ensured by the propositions $$T_W>{T^{″}}_W$$, $${T^{″}}_0=T_0$$ and also by that fact, that the loss entropy $$H(X|Y)$$ is described and given by the heat $$\mathrm{\Delta }{Q}_0=\mathrm{\Delta }{Q^{″}}_0$$. But by our combined cycle $$O{O}^{″}$$ it is valid too that

$$H(X)=\frac{\mathrm{\Delta }{Q}_W}{\text{k}{T}_W}=\frac{\mathrm{\Delta }{Q^{″}}_W}{\text{k}{T^{″}}_W}=H(Y^{″}\mathrm{<mo\; stretchy="false">)</mo><mi>\; </mi><mi>\; </mi>}\left[=\frac{\mathrm{\Delta }{Q^{″}}_W}{\text{k}{T}_0{}^{*}}\right]$$E33

and by both parts of (4) we have

$$\frac{H(X|Y)}{H(Y^{″}|X^{″})}={\beta }^{*}<1$$E34

For the whole information entropy $$\mathrm{\Delta }{A}^{*}/\text{k}{T}_W$$ (the whole thermodynamic entropy $$S_C$$ in information units) and by following the previous relations also it is valid that

$$\begin{array}{l}\frac{\mathrm{\Delta }{A}^{*}}{\text{k}{T}_W}=H(Y^{″})-H(Y^{″})\cdot {\beta }^{*}=H(Y^{″})\cdot \left(1-\frac{T_0{}^{*}}{T_W}\right)\\ =H(Y^{″})\cdot \left[1-\frac{H(X|Y)}{H(X^{″}|Y^{″})}\right]\end{array}$$E35

And thus, the structure of the information transfer channel $$K$$ (expressed by the quantity $$H(X|Y)$$) is measurable by the value $$H^{*}(Y^{*})$$ from (20), (32) and (35). Symbolicaly, we can write, using a growing function $$f$$,

$$H^{*}(Y^{*}\mathrm{<mo\; stretchy="false">)</mo><mi>\; </mi><mo>=</mo><mi>\; </mi>}\frac{\mathrm{\Delta }{A}^{*}}{\text{k}{T}_W}\cong f\left[H(X|Y)\right]>0$$E36

The cycles $$O$$, $$O^{″}$$ and $$O{O}^{″}$$ are the Carnot Cycles and thus, from their definition and construction they are, imaginatively

When an infinite reserve of energy would exist.

in principle, the infinite cycles; in each of them the following criterion of an infinite cycle (see [14]) it is valid inevitably,

$$T\left(X^{[\cdot ]};Y^{[\cdot ]}\right)=H\left(X^{[\cdot ]}\right)-H\left(X^{[\cdot ]}|Y^{[\cdot ]}\right)=H\left(Y^{[\cdot ]}\right)>0\mathrm{and}\mathrm{\Delta }{S}_L^{[\cdot ]}=0$$E37

The construction of the cycle $$O{O}^{″}$$ enables us to recognize that the infinite cycle $$O$$ is running; the unsolvable case of the Auto-Reference in $$O{O}^{″}$$ occurs just when and only when

$$T_W={T^{″}}_W\mathrm{,}\left[\left[T_W={T^{″}}_W\right]\Rightarrow \left[H^{*}(Y^{*})=0\right]\right]$$E38

(Thus, when we contemporarily await anything else than the zero output or an output which is not relevant to the given input, by this only awaiting, we require a construction of the Perpetuum Mobile functionality.)

Our observation of the process $$O$$ now being considered as a model or as the realization of the computing process $$\overrightarrow{\kappa }$$ in a certain Turing Machine $$TM$$ or an information transfer $$T$$ in a certain channel $$K$$ - the measuring of a transferring structure expressed by the value of the quantity $$H(X|Y)$$, is thus possible but only by another process with a certain ’step-aside’ from the observed process $$O$$ in-built, with a certain ’mirror’ $$O^{″}\cong T^{″}$$, with the aids of another transferring structure expressed by the value of the quantity $$H(X^{″}|Y^{″})$$.

From the both processes, the cycles $$O$$ and $$O^{″}$$, the whole combined and one cycle $$O{O}^{″}$$ is created to be modeling the whole and one transfer channel $$K{K}^{″}$$ in which the observed, the measured property, the value $$H(X|Y)$$ in the given ’time click’ $$p$$ (the click, the interval) expressing the structure of the channel $$K$$ is one of the ingoing (input) messages (informations). The resulting double cycle $$O{O}^{″}$$ performs as a direct Carnot Cycle with the working temperatures $$T_W$$ and $$T^{*}{}_0$$, $$T_W>T^{*}{}_0$$, $${T^{″}}_W=T^{*}{}_0$$.

The required ’step-aside’ is created by the difference $$T_W-T^{*}{}_0>0$$. The whole information entropy (the thermodynamic entropy in information units) of the whole isolated system in which our double cycle $$O{O}^{″}$$ is running, the whole output information $$H^{*}(Y^{*})$$ of this double cycle $$O{O}^{″}$$ is then a certain function $$f(\cdot )$$ of the measure $$H(X|Y)$$ of the structure being measured (observed) and as such, of the value of the argument $$H(X|Y)$$ from the relation (36).

Remark: Also the following consideration is possible: We use the change $$H(Y)$$ of the output entropy of the observed process $$O$$ as its reaction to a change $$H(X)$$ of the input entropy and just by the evidenced $$H(X|Y)$$. Our measuring is then characterized, in the same sense as in (36) and (37), by the whole value

$$H(X)\cdot \left(1-\beta \right)-H(X)\cdot \left(1-{\beta }^{″}\right)=H(X)\cdot {\frac{T_0}{T^{″}}}_W\cdot \left(1-\frac{{T^{″}}_W}{T_W}\right)>0$$BB4

Now it is obvious that the transferring (copying, measuring, observing) of the structure of the channel $$K$$ is possible then and only then a certain structural ’step-aside’ between the observed object (the transferred or the measured structure, now and here the structure of a transfer channel $$K$$) and the observing process (the channel $$K^{″}$$ with the transferring process $$T^{″}$$) expressed by the nonzero and positive values of the difference (2) is possible.

By the term ’step-aside’ of the observing computing process (let us denote it as $${\overrightarrow{\kappa }}^{″}$$) from the observed computing process (let us denote it as $$\overrightarrow{\kappa }$$) we understand a time delay between them, better said, it is a tracing

In the programmers’ manner or language: listing, cross-reference, memory dump.

of the observed computing process $$\overrightarrow{\kappa }$$.

4. Turing Computing, Auto-Reference and Halting Problem

Turing Machine ($$TM$$) is driven by a program which is interpreted by its Control Unit ($$C{U}_{TM}$$). The Control Unit $$C{U}_{TM}$$ is a finite automaton (Mealy’s or Moore’s sequential machine). The program for the $$TM$$ consists of the finite sequence $$\overrightarrow{\eta }$$ of instructions $${\eta }_{[\cdot ]}$$,

$$\overrightarrow{\eta }={\left({\eta }_q\right)}_{q=1}^{q\in \mathbb{N}}={\left[{\left(s_i\mathrm{,}{x}_k\mathrm{,}{s}_j\mathrm{,}{y}_l\mathrm{,}D\right)}_q\right]}_{q=1}^{q\in \mathbb{N}}\mathrm{,}\left|\overrightarrow{\eta }\right|\in \text{N}$$E39

Each of these instructions describes an overwriting rule of a regular grammar [15, 19, 21],

$$s_i\to \left(x_k\mathrm{,}{y}_l\mathrm{,}D\right)s_j$$E40

performed in the given step (time, moment) $$p$$, $$p\in \mathbb{N}$$, of the $$TM$$ ’s activity;

• $$s_i$$ is the $$i$$ -th nonterminal symbol of the regular grammar, or, respectively, it is a status of the $$C{U}_{TM}$$ within the actual step $$p\in \mathbb{N}$$ of the $$TM$$ ’s activity,

• $$x_k$$ is an input terminal symbol being read from the input-output tape of the $$TM$$ within the actual step $$p$$ of the $$TM$$ ’s activity,

• $$y_l$$ is an output terminal symbol by which the $$C{U}_{TM}$$ overwrites the symbol $$x_k$$ which has been read (in the actual step $$p$$ of the $$TM$$ ’s activity),

• $$s_j$$ is the successive status of the $$C{U}_{TM}$$, given by the instruction for the following step $$p+1$$ of the $$C{U}_{TM}$$.

Within the actual step $$p$$ of the $$TM$$ ’s activity the $$C{U}_{TM}$$ is changing its status to $$s_j$$ [this change is based on the status $$s_i$$, and the symbol $$x_k$$ has been read $$(s_i\stackrel{x_k}{\to }{s}_j)$$], and is performing the transformation

$$x_k\to y_l$$E41

on the scanned (actual) position of the input-output tape,

• $$D$$ determines the moving direction of the read-write head of the $$C{U}_{TM}$$ after the symbol $$y_l$$ has been recorded [in the status $$s_{j_p}$$ ($$s_{j_p}$$ denotes $$s_j$$ for the step $$p$$) used further on as the following one, $$s_{j_p}\stackrel{\text{Def}}{=}{s}_{i_{p+1}}$$], $$D\in \left\{L\mathrm{,}R\right\}$$.

The value $$L$$ or $$R$$ of the symbol $$D$$ determines the left slip or the right slip from the actual position on the input-output tape to its (left or right) neighbor after the transformation $$x_k$$ to $$y_l$$ has been performed.

The oriented edge of the transition graph of the $$C{U}_{TM}$$ (the finite automaton) is described by the symbol $$s_i\stackrel{(x_k\mathrm{,}{y}_l\mathrm{,}D)}{\to }{s}_j$$. The $$TM$$ ’s activity generates a sequence of the instructions having been performed in steps $$p$$, $${\left[(s_{i_p}\mathrm{,}{x}_{k_p}\mathrm{,}{s}_{j_p}\mathrm{,}{y}_{l_p}\mathrm{,}{D}_p)\right]}_{p=1}^{p=p_{\text{last}}}$$,

$$s_{i_p}\stackrel{(x_{k_p}\mathrm{,}{y}_{l_p}\mathrm{,}{D}_p)}{\to }{s}_{j_p}\mathrm{,}\mathrm{further}\mathrm{on}{s}_{j_p}=s_{i_{p+1}}$$E42

(the edge of the oriented transition graph of the $$C{U}_{TM}$$ in the step $$p$$), by which the computing process $$(\overrightarrow{\kappa })$$ has gone through (from the first step $$p=1$$ till, for this while, the last step $$p=p_{\text{last}}$$ of the $$TM$$ ’s activity). They are also the overwriting rules of the regular grammar, being performed within each step $$p\mathrm{,}p\ge 1$$,

$$s_{i_p}\to \left(x_{k_p}\mathrm{,}{y}_{l_p}\mathrm{,}{D}_p\right)s_{j_p}\mathrm{,}{s}_{j_p}=s_{i_{p+1}}$$E43

By this way a regular language of the words $$(x_{k_p}\mathrm{,}{y}_{l_p}\mathrm{,}{D}_p)$$ or, respectively, a regular language of the instructions $$(s_{i_p}\mathrm{,}{x}_{k_p}\mathrm{,}{s}_{j_p}\mathrm{,}{y}_{l_p}\mathrm{,}{D}_p)$$ having been performed is defined. This second regular language is describable by the rules (of a regular grammar)

$$S_{i_p}\to \left(s_{i_p}\mathrm{,}{x}_{k_p}\mathrm{,}{s}_{j_p}\mathrm{,}{y}_{l_p}\mathrm{,}{D}_p\right)S_{j_p}\mathrm{,}{S}_{j_p}\stackrel{\text{Def}}{=}{S}_{i_{p+1}}$$E44

being applied in each step $$p\ge 1$$ of the $$TM$$ ’s activity. Thus, this language is to be acceptable by a certain finite automaton with $$n$$ states $$S_{[\cdot ]}$$.

When this language is infinite

Better said, having the arbitrary (but finite) length.

(the infinite chain of instructions of the finite length), such its word

$${\left[\left(s_{i_1}\mathrm{,}{x}_{k_1}\mathrm{,}{s}_{j_1}\mathrm{,}{y}_{l_1}\mathrm{,}{D}_1\right)\mathrm{,<mi>\; </mi>...,}\left(s_{i_p}\mathrm{,}{x}_{k_p}\mathrm{,}{s}_{j_p}\mathrm{,}{y}_{l_p}\mathrm{,}{D}_p\right)\right]}_{p=l}$$E45

of the length $$l$$ exists that for that finite automaton [with $$n$$ states $$S_{[\cdot ]}$$ and the transition rules (42) or (44)] the Pumping Lemma [19, 21] it is valid

$$n\le l\mathrm{<mi>\; </mi><mo><</mo><mi>\; </mi>2}n$$E46

4.1. Auto-Reference in Turing Computing

Although any instruction of the Turing Machine $$TM$$ describes one step of the computing process in this $$TM$$, it is considerable as a description (of one step) of an information transfer process running in a certain transfer channel $$K$$ ; we postulate the relation $$TM\cong K$$. The computing process in the $$TM$$ is, also, a transfer process in a channel $$K$$. For $$K\cong O$$ it is valid that $$TM\cong O$$.

In each step $$p>1$$ of its activity, the $$TM\cong K$$ is accepting its own configuration from the previous step $$p-1$$ as its input, includes its contemporary status ($$s_{i_p}=s_{j_{p-1}}$$) and generates its status [$$s_{i_{(p+1)}}$$] and the configuration for the next step $$p+1$$, etc.

$$(s_{i_p}\mathrm{,}{x}_{k_p}\mathrm{,}{s}_{j_p}\mathrm{,}{y}_{l_p}\mathrm{,}{D}_p)(\overrightarrow{{\sigma }_p}\mathrm{,}{s}_p\mathrm{,}\overrightarrow{{\rho }_p})\to (\overrightarrow{{\sigma }_{p+1}}\mathrm{,}{s}_{i_{p+1}}\mathrm{,}\overrightarrow{{\rho }_{p+1}})$$, see further.

Similarly it is valid for the configurations (denoted now by $$X_p$$ and $$Y_p$$), see further on.

For each $$p\ge 1$$ we consider the actual instances of the stochastic quantities

’$$⊑$$’ now denotes the substring from the beginning of the string.

$$X\mathrm{,}Y$$,

$$\begin{array}{l}X\triangleq X_p\mathrm{,}Y\triangleq Y_p\mathrm{<mo>;</mo><mi>\; </mi><mi>\; </mi>}X|Y\triangleq X_p|Y_p\mathrm{,}Y|X\triangleq Y_p|X_p\mathrm{<mo>;</mo><mi>\; </mi><mi>\; </mi>}{Y}_p=X_{p+1}\\ X_p|X_{p+1}\triangleq X_p⊑X_p{X}_{p+1}\mathrm{,}{X}_{p+1}|X_p\stackrel{\mathrm{\Delta }}{=}{X}_{p+1}⊑{\left(X_p{X}_{p+1}\right)}^{-1}\end{array}$$E47

In any step $$p$$ of the $$TM$$ ’s activity its own configurations $$({\overrightarrow{\sigma }}_{p_{}}\mathrm{,}{s}_p\mathrm{,}{\overrightarrow{\rho }}_{p_{}})$$ - members of the sequence - of the computing process $$\overrightarrow{\kappa }\stackrel{\text{Def}}{=}{[({\overrightarrow{\sigma }}_{p_{}}\mathrm{,}{s}_p\mathrm{,}{\overrightarrow{\rho }}_p)]}_{p=1}^{p\mathrm{<mo>=</mo><mi>\; </mi>...}}$$, can be considered as follows;

• let now the stochastic quantity $$X_p$$ be realized by the chain

$$\left({\overrightarrow{\sigma }}_p\mathrm{,}{s}_p\mathrm{,}{\overrightarrow{\rho }}_p\right)\in T^{*}\times S_{}\times T^{*}\mathrm{<mo>;</mo><mi>\; </mi><mi>\; </mi>}p\mathrm{<mo>=</mo>1,<mi>\; </mi><mi>\; </mi>}{\overrightarrow{\sigma }}_1=\overrightarrow{\epsilon }a{\overrightarrow{\rho }}_1=\overrightarrow{\xi }\mathrm{,}{s}_p=s_0$$E48

• let now the stochastic quantity $$Y_p$$ be realized by the chain

$$\left[{\overrightarrow{\sigma }}_{p+1}\mathrm{,}{s}_{p+)}\mathrm{,}{\overrightarrow{\rho }}_{p+1}\right]\in T^{*}\times S_{}\times T^{*}$$E49

Then, the computing process in the $$TM\cong K$$ is describable informationally,

The transitions are given by the $${\eta }_{q_p}$$ called by $$X_p\mathrm{<mo>;</mo><mi>\; </mi><mi>\; </mi>}{X}_p|X_{p+1}\to {\eta }_{q_p}\mathrm{,}[{\eta }_{q_p}^{-1}(X_{p+1})=X_p]$$.

$${\eta }_{q_p}^{-1}(X_{p+1})=X_p$$ - comparison of the structures of the $$X_p$$ and the $$X_{p+1}$$ (in $$X_p|X_{p+1}$$).

$$\begin{array}{c}H(X)\triangleq H(X_p)=H\left(\overrightarrow{{\sigma }_p}\mathrm{,}{s}_p\mathrm{,}\overrightarrow{{\rho }_p}\right)\\ H(Y)\triangleq H(Y_p)=H\left[X_{p+1}\right]=H\left[\overrightarrow{{\overrightarrow{\sigma }}_{p+1}}\mathrm{,}{s}_{p+1}\mathrm{,}\overrightarrow{{\rho }_{p+1}}\right]\\ H(X|Y)\triangleq H\left(X_p|Y_p\right)=H\left[X_p|X_{p+1}\right]\mathrm{,}H\left(Y|X\right)\triangleq H\left(Y_p|X_p\right)=H\left[X_{p+1}|X_p\right]\\ T(X;Y)\triangleq T\left(X_p;Y_p\right)=H\left(X_p\right)-H\left[X_p|X_{p+1}\right]\\ =H\left(\overrightarrow{{\sigma }_p}\mathrm{,}{s}_p\mathrm{,}\overrightarrow{{\rho }_p}\right)-H\left[\left(\overrightarrow{{\sigma }_p}\mathrm{,}{s}_p\mathrm{,}\overrightarrow{{\rho }_p}\right)|\left[\overrightarrow{{\sigma }_{p+1}}\mathrm{,}{s}_{p+1}\mathrm{,}\overrightarrow{{\rho }_{p+1}}\right]\right]\\ T(Y;X)\triangleq T\left(Y_p;X_p\right)=H\left(X_{p+1}\right)-H\left[X_{p+1}|X_p\right]\\ =H\left[\overrightarrow{{\sigma }_{p+1}}\mathrm{,}{s}_{p+1}\mathrm{,}\overrightarrow{{\rho }_{p+1}}\right]-H\left[\overrightarrow{{\sigma }_{p+1}}\mathrm{,}{s}_{p+1}\mathrm{,}\overrightarrow{{\rho }_{p+1}}]|\left(\overrightarrow{{\sigma }_p}\mathrm{,}{s}_p\mathrm{,}\overrightarrow{{\rho }_p}\right)\right]\end{array}$$E50

The Auto-Reference arises with the following description of the computing (transfer, observation) process when, e.g., for a certain $$p\ge p^{*}\ge 1$$,

$$\begin{array}{l}H(X_p)-H\left[X_p|X_{p+1}\right]=H(X_{p+1})-H\left[X_{p+1}|X_p\right]\mathrm{,}p\ge 1\\ H(X_p)=H\left(X_p|X_{p+1}\right)\mathrm{<mo>;</mo><mi>\; </mi><mi>\; </mi>}{X}_p=X_p⊑X_{p+1}\mathrm{,}{X}_{p+1}=\epsilon \\ H(X_{p+1})=H\left(X_{p+1}|X_p\right)\mathrm{,}\left[H\left[X_{p+1}|X_p\right]=0\right]\end{array}$$E51

This way of considerations ’constructs’ the $$TM$$ ’s infinite cycle from the programmer’s point of view, Self-Observation in an information point of view and a stationary status from the thermodynamics point of view.

In any case a ’step-aside’ to gain something else than the zero output is required.

By the ’step-aside’ of the observing computing process from the observed computing process we mean a time delay between those two processes or, better said, a staging of the trace of the observed process.

4.2. Halting Problem as Auto-Reference

Now we are considering a certain $$TM$$ (the observed machine) being driven by a program $$\overrightarrow{\eta }$$ and working with a certain input word $$\overrightarrow{\xi }$$. Let this activity be described by the word $$[\overrightarrow{\text{d}(TM)}]$$.

Let us consider that the $$TM$$ with the input word $$\overrightarrow{\xi }$$

• halts, $${\begin{array}{l}HALT\hfill \end{array}}_{TM}$$, whether the word $$\overrightarrow{\xi }$$ is accepted or rejected,

$$HAL{T}_{TM}=\left\{HAL{T}_{TM}^{\text{Accept}}\cup HAL{T}_{TM}^{\text{Reject}}\right\}$$E52

• does not halt, $$LOO{P}_{TM}^{\infty }$$ (the $$TM$$ ’s infinite cycle)

Let us construct the three new Turing Machines $$M_1$$, $$M_2$$ and $$M_3$$ as follows [18]

Minski’s proof for the undecidability of the Halting Problem (Entscheidungsproblem type).

• $$M_1$$ works with the input word $$[\overrightarrow{\text{d}(TM)}*\overrightarrow{\xi }]$$ in that way that

• halts, $$\begin{array}{l}HALT\hfill \end{array}{}_{M{}_1}^{\text{Accept}}$$,

• stops, $${\begin{array}{l}HALT\hfill \end{array}}_{M{}_1}^{\text{Reject}}$$,

$$HAL{T}_{M{}_1}^{\text{Accept}}\Leftarrow HAL{T}_{TM}\mathrm{,}HAL{T}_{M{}_1}^{\text{Reject}}\Leftarrow LOO{P}_{TM}^{\infty }$$E53

• $$M_2$$ modifies the activity of the $$M_1$$ in that way, that the input word which is being worked with is $$[\overrightarrow{\text{d}(TM)}*\overrightarrow{\xi }]$$ and

• halts, $$\begin{array}{l}HALT\hfill \end{array}{}_{M{}_2}$$,

• does not halt, $$LOO{P}_{M{}_2}^{\infty }$$,

$$\begin{array}{l}HAL{T}_{M{}_2}\Leftarrow LOO{P}_{TM}^{\infty }\left[\Rightarrow HAL{T}_{M{}_1}^{\text{Reject}}\right]\\ LOO{P}_{M{}_2}^{\infty }\Leftarrow HAL{T}_{TM}\left[\Rightarrow HAL{T}_{M{}_1}^{\text{Accept}}\right]\end{array}$$E54

• $$M_3$$ is an ’extension’ of the $$M_2$$ : it doubles its own input word $$[\overrightarrow{\text{d}(TM)}]$$ into $$[\overrightarrow{\text{d}(TM)}*\overrightarrow{\text{d}(TM)}]$$ and gives it to the input (of its sub-machine) $$M_2$$ and

• halts, $${\begin{array}{l}HALT\hfill \end{array}}_{M{}_3}$$,

• does not halt, $$LOO{P}_{M{}_3}^{\infty }$$,

$$\begin{array}{l}HAL{T}_{M_3}\equiv HAL{T}_{M_2}\Leftarrow LOO{P}_{TM}^{\infty }\left[\Rightarrow HAL{T}_{M_1}^{\text{Reject}}\right]\\ LOO{P}_{M_3}^{\infty }\equiv LOO{P}_{M_2}^{\infty }\Leftarrow HAL{T}_{TM}\left[\Rightarrow HAL{T}_{M{}_1}^{\text{Accept}}\right]\end{array}$$E55

• But, when the machine $$M_3\equiv TM$$ accepts the description $$\overrightarrow{d(M_3)}$$, thus it is valid that $$\overrightarrow{d(M_3)}\equiv \overrightarrow{\text{d}(TM)}$$, then

$$\begin{array}{c}\left[HAL{T}_{TM}\Leftarrow LOO{P}_{TM}^{\infty }\right]\wedge \left[LOO{P}_{TM}^{\infty }\Leftarrow HAL{T}_{TM}\right]\\ \equiv \\ HAL{T}_{TM}\iff LOO{P}_{TM}^{\infty }\end{array}$$E56

This result (56) is the contradiction. It is the consequence of the Cantor diagonal argument having been used carrying the Auto-Reference to the sequence of the machines $$\left(TM\mathrm{,}{M}_1\mathrm{,}{M}_2\mathrm{,}{M}_3\right)$$, or, respectively, to the sequence of the machines $$\left(TM\mathrm{,}{M}_3\right)$$,

$$\left(\underset{\_}{TM}\mathrm{,}{M}_3\equiv \underset{\_}{TM}\right)$$E57

and is leading us to that opinion that the proposition about the decidability of the Halting Problem (recognizing the $$LOO{P}_{TM}^{\infty }$$ state) is not right.

In any given step $$p\ge 1$$ the machine $$TM$$ is deciding about itself (it is working with the description of its own actual status), it is the channel ’transferring’ its own structure, it is the Self-Observer. Thus it is in a stationary status in the thermodynamic point of view.

Within this point of view, we can envisage two identical, but reversed mutually, ideal Carnot Cycles connected together. In this sense, these two machine $$O$$ and $$O^{″}$$ create the equilibrium system $$O{O}^{″}$$, in which we introduce the term stationary status.

Within such a system the (infinitesimal) part of heat is circulating through the whole combined machine $$O{O}^{″}$$. Let this fact be now the thermodynamic model of the infinite cycle being started by the Self-Observation, by the Auto-Reference action (56), (57); one run is like an uninterruptable operation.

The recursive call of the function $$\overrightarrow{\text{d}(TM)}$$ (of the machine $$TM$$) by the same function $$\overrightarrow{\text{d}(TM)}$$ (by the machine $$TM$$) with the same argument $$\left[\overrightarrow{\text{d}(TM)}*\overrightarrow{\text{d}(TM)}\right]$$ is now given. The Auto-Reference (56), (57) is then the generative function for the infinite sequences, nevertheless thought only, as the consequence of the stationarity concept in-built in this type of consideration,

$$\begin{array}{c}\left(TM\mathrm{,}TM\mathrm{,<mi>\; </mi>...,<mi>\; </mi>}TM\mathrm{,<mi>\; </mi>...<mi>\; </mi>}\right)\triangleq {\left(T{M}_{\mathrm{\Delta }{t}_p}\right)}_{p=1}^{\infty }\\ \left[\text{d}(TM)\mathrm{,}\text{d}(TM\mathrm{<mo\; stretchy="false">)</mo>,<mi>\; </mi>...,<mi>\; </mi>}\text{d}(TM\mathrm{<mo\; stretchy="false">)</mo>,<mi>\; </mi>...<mi>\; </mi>}\right]\triangleq {\left[{\left[\text{d}(TM)\right]}_{\mathrm{\Delta }{t}_p}\right]}_{p=1}^{\infty }\\ \left[HAL{T}_{TM}^{\infty }\mathrm{,}HAL{T}_{TM}^{\infty }\mathrm{,<mi>\; </mi>...,<mi>\; </mi>}HAL{T}_{TM}^{\infty }\mathrm{,<mi>\; </mi>...<mi>\; </mi>}\right]\triangleq {\left[{\left(HAL{T}_{TM}^{\infty }\right)}_{\mathrm{\Delta }{t}_p}\right]}_{p=1}^{\infty }\\ \left[LOO{P}_{TM}^{\infty }\mathrm{,}LOO{P}_{TM}^{\infty }\mathrm{,<mi>\; </mi>...,<mi>\; </mi>}LOO{P}_{TM}^{\infty }\mathrm{,<mi>\; </mi>...<mi>\; </mi>}\right]\triangleq {\left[{\left(LOO{P}_{TM}^{\infty }\right)}_{\mathrm{\Delta }{t}_p}\right]}_{p=1}^{\infty }\end{array}$$E58

We envisage, within this time-expansion of the (56) or (57) [which possibility follows from the (quasi)stationarity concept], the infinite cycle in the observed machine $$TM$$ arises, based on its Self-Description $$\left[\overrightarrow{\xi }\right]\equiv \left[\overrightarrow{\text{d}(TM)}\right]$$. But, following the Auto-Reference construction, it ’runs’ in the double-machine $$(TM\mathrm{,}{M}_3\equiv TM)\cong O{O}^{″}$$.

Generally, the cycle $$O{O}^{″}$$ is considered as the reversible only.

The Auto-Reference step that is to solve the Halting solve the Halting Problem proves, only, its own disusability creates just a certain image of what is to be possibly discovered - the infinite cycle in the form of the infinite constant time sequences [when the time expansion (58) for $$p\ge 1$$ is considered].

As it is valid for any stationary status, also this one can be ceased or can be excluded by an external action, by the ’step-aside’, by the staging as follows.

5. Concept Removing Halting Problem

We suppose that in the case of a computing process running in a $$TM$$ its status $$LOO{P}_{TM}^{\infty }$$ (the infinite cycle) is decidable within the Observing Turing Machine ($$OTM$$) by using the $$T{M}^{\prime }s$$ trace. By this trace, the machine $$OTM$$ generates and controls the ’combined observing process’ for the process in the $$TM$$.

We will show and use the fact, that certain regular sequences are generated. If they are infinite, they are, inevitably, periodical; as such, they are decidable languages for their infinity [1].

We will use the alphabet of terminal symbols $$T=\left\{I\mathrm{,}B\right\}$$ and these structures:

• $$(s_i\mathrm{,}{x}_k\mathrm{,}{s}_j\mathrm{,}{y}_l\mathrm{,}D)$$ is the instruction

• $$(\overrightarrow{\sigma }\mathrm{,}{s}_{[\cdot ]}\mathrm{,}\overrightarrow{\rho })$$ is the configuration

• $$\left(\epsilon \left[\sigma \mathrm{,}{s}_{[\cdot ]}\mathrm{,}\rho \right]\epsilon \right)$$ is the configuration type

Further, we introduce the general configuration type $$X$$ ;

• $$X=(\overrightarrow{\sigma }\mathrm{,}{s}_{[\cdot ]}\mathrm{,}\overrightarrow{\rho })\triangleq (B\sigma \mathrm{,}{s}_{[\cdot ]}\mathrm{,}\rho B)$$.

By this general configuration type the chains, e.g. $$B\overrightarrow{IB}{s}_{[\cdot ]}\overrightarrow{BI}B$$ are ment,

$$\begin{array}{c}B\overrightarrow{IB}{s}_{[\cdot ]}\overrightarrow{BI}B=BBBBIIIIBBBBIIIIIBBB{s}_{[\cdot ]}BBIIBBBIIIBBBB\\ \in \left(\overrightarrow{\sigma }\mathrm{,}{s}_{[\cdot ]}\mathrm{,}\overrightarrow{\rho }\right)\end{array}$$BB5

The computing process in the observed $$TM$$ generates the grammar of a regular language of instructions and, also, of general types of configurations especially, infinite possibly, and thus cyclical. As such, they are decidable languages for their infinity.

These grammars are given by the initial input $$\overrightarrow{\xi }$$, or, respectively, by the initial configuration $$(\epsilon \mathrm{,}{s}_0\mathrm{,}\overrightarrow{\xi })$$ and, also, by the instructions $${\eta }_{q_p}$$ of the programme $$\overrightarrow{\eta }$$, being generated by the sequence of the steps $$p$$ of the $$TM$$ ’s activity in which the $$TM$$ instructions are interpreted. This sequence itself is pressed out by the configurations having been generated (See Appendix).

The Auto-Reference arises when, e.g., for a certain $$p\ge p*\ge p^0\ge 1$$,

$$\begin{array}{c}H\left(\overrightarrow{X_p}\right)-H\left(\overrightarrow{X_p}|\overrightarrow{X_{p+1}}\right)=H\left(\overrightarrow{X{}_{p+1}}\right)-H\left(\overrightarrow{X{}_{p+1}}|\overrightarrow{X_p}\right)=0\\ \overrightarrow{X_p}\triangleq \left(X_{p*}\mathrm{,}{X}_{p*+1}\mathrm{,<mi>\; </mi>...<mi>\; </mi>},X_p\right)\\ \overrightarrow{X_{p+1}}\triangleq \left(\overrightarrow{X_p}\mathrm{,}{X}_{p+1}\mathrm{,<mi>\; </mi>...,}{X}_{2p+2-p*}\right)\equiv \left(\overrightarrow{X_p}\overrightarrow{X_p}\right)\end{array}$$E59

Also we can write [the similar is writable for (22), (23); also see the remark 7].

$$\begin{array}{l}\overrightarrow{X_p}-\left(\overrightarrow{X{}_p}⊑\overrightarrow{X_{p+1}}\right)=\overrightarrow{X_{p+1}}-\left(\overrightarrow{X{}_p}⊑{\overrightarrow{X_{p+1}}}^{-1}\right)=\epsilon \\ \overrightarrow{X_p}=\left(\overrightarrow{X_p}⊑\overrightarrow{X_{p+1}}\right)=\left(\overrightarrow{X_p}⊑{\overrightarrow{X_{p+1}}}^{-1}\right)\\ H\left(\overrightarrow{X_p}\right)=\left(\overrightarrow{X_p}⊑\overrightarrow{X_{p+1}}\right)=H\left(\overrightarrow{X_p}⊑{\overrightarrow{X_{p+1}}}^{-1}\right)=H\left(\overrightarrow{X_{p+1}}⊑\overrightarrow{X_p}\right)=0\\ \left[H\left(\overrightarrow{X_{p+1}}\right)=0\right]\iff \left[Pr\left(\overrightarrow{X_p}\right)=Pr\left(\overrightarrow{X_p}\overrightarrow{X_p}\right)=Pr\left({\left[\overrightarrow{X_p}\right]}^{+}\right)=1\right]\end{array}$$E60

where $$Pr(\cdot )$$ denotes probability.

5.1. Method - the $$OTM$$

$${✠}^1$$ Let the Turing Machine be driven by the program $$\overrightarrow{\eta }$$, do a certain number $$e\cdot P$$ of instructions $${\eta }_{[\cdot ]}$$ (of the program $$\overrightarrow{\eta }$$) beginning from the initial configuration $$(\epsilon \mathrm{,}{s}_0\mathrm{,}\overrightarrow{\xi })$$. Let, e.g., $$P=2l+\mathrm{1,}l=|\overrightarrow{\xi }\mathrm{<mo>|</mo>,<mi>\; </mi><mi>\; </mi>}e\ge 1$$ ; $$e\in \text{N}$$ be the number of the stage (for each stage we write, in a programmer style, $$e:=e+1$$)

• The step $${✠}^1$$ generates the table of nine-partite structures. Its length of $$e\cdot P$$ rows,

  The symbols '[' and ']' in the tables denote the range of the input (its limits) and, also, the ’operating space’ for the $$C{U}_{TM}$$ in each step.

$${\left[p\parallel q\parallel s_i{x}_k{s}_j{y}_{l}D\parallel \left[\overrightarrow{\sigma }{s}_{[\cdot ]}\overrightarrow{\rho }\right]\parallel C\parallel \parallel \left(\epsilon \left[\sigma \mathrm{,}{s}_{[\cdot ]}\mathrm{,}\rho \right]\epsilon \right)\parallel g\parallel \overrightarrow{\sigma }{s}_{[\cdot ]}\overrightarrow{\rho }\parallel m\right]}_{p=1}^{p=e\mathrm{.}P}$$E61

where the denotation used is

• $$C$$ is the number of the configuration $$(\overrightarrow{\sigma }\mathrm{,}{s}_{[\cdot ]}\mathrm{,}\overrightarrow{\rho })$$

• $$g$$ is the number of the configuration type $$(\epsilon (\sigma \mathrm{,}{s}_{[\cdot ]}\mathrm{,}\rho )\epsilon )$$

• $$m$$ is the number of the general configuration type $$G$$, $$(\overrightarrow{\sigma }\mathrm{,}{s}_{[\cdot ]}\mathrm{,}\overrightarrow{\rho })$$

$${✠}^2$$ In the table ($${✠}^1$$) we are seeking two successive blocks of rows limited by those rows having the identical values in the columns (the identical six-partite structures)

$$\left[q\parallel s_i{x}_k{s}_j{y}_{l}D\parallel \left(\epsilon \left[\sigma \mathrm{,}{s}_{[\cdot ]}\mathrm{,}\rho \right]\epsilon \right)\parallel g\parallel \overrightarrow{\sigma }{s}_{[\cdot ]}\overrightarrow{\rho }\parallel m\right]$$E62

Thus, we are seeking for (the sequence of) the three rows being identical in those columns while the last row of the first block is the first row of the second block [this second ends by the third row (identical in the six columns considered)]. The numbers of these separating rows, the first, the second and the third row are the numbers of steps $$p_{[\cdot ]}\mathrm{,}{p}_{[\cdot \cdot ]}$$ and $$p_{[\cdot \cdot \cdot ]}$$ of the observed computing process. These rows are separated by numbers

$$\mathrm{\Delta }{p}_{[\cdot ]}\triangleq p_{[\cdot \cdot ]}-p_{[\cdot ]}-1\ge \mathrm{0,}\mathrm{\Delta }{p}_{[\cdot \cdot ]}\triangleq p_{[\cdot \cdot \cdot ]}-p_{[\cdot \cdot ]}-1\ge 0$$E63

of rows lying between them. (They can follow immediately, $$\mathrm{\Delta }{p}_{[\cdot ]}=\mathrm{0,}\mathrm{\Delta }{p}_{[\cdot \cdot ]}=0$$.)

$${✠}^3$$ If the three separating rows are not found within the given stage $$e$$ ($${✠}^2$$), we start the computing process driven by the program $$\overrightarrow{\eta }$$, and its tracing, from the beginning [$$(\epsilon \mathrm{,}{s}_0\mathrm{,}\overrightarrow{\xi })$$, ($${✠}^1$$)], and let it run $$e\cdot P$$ steps, where $$e:=e+1$$ is set down.

$${✠}^4$$ If those three separating rows are found within the given stage $$e$$ ($${✠}^2$$) (those two blocks covering the rows $$p_{[\cdot ]}\mathrm{,<mi>\; </mi>...,<mi>\; </mi>}{p}_{[\cdot \cdot \cdot ]}$$ where $$p_{[\cdot \cdot \cdot ]}=p_{[\cdot \cdot ]}+\mathrm{\Delta }{p}_{[\cdot \cdot ]}+1$$ and $$p_{[\cdot \cdot ]}=p_{[\cdot ]}+\mathrm{\Delta }{p}_{[\cdot ]}+1$$) we are checking both the two blocks, each of them from its beginning ($$p_{[\cdot ]}$$, or $$p_{[\cdot \cdot ]}$$ respectively) till its end ($$p_{[\cdot \cdot ]}$$, or $$p_{[\cdot \cdot \cdot ]}$$ respectively), seeking the rows with the identical values within their six columns (62),

If these blocks are identical the infinite cycle is discovered, but we continue uniformly with $${✠}^5$$.

$$\left[q\parallel s_i{x}_k{s}_j{y}_{l}D\parallel \left(\epsilon \left[\sigma \mathrm{,}{s}_{[\cdot ]}\mathrm{,}\rho \right]\epsilon \right)\parallel g\parallel \overrightarrow{\sigma }{s}_{[\cdot ]}\overrightarrow{\rho }\parallel m\right]$$BB6

$${✠}^5$$ Two or more such identical six-partite structures on the successive row positions (denoted by symbols $$z$$ and $$m$$) are considered as the only one row

$$\begin{array}{l}1)z_{[\cdot ]}\mathrm{,<mi>\; </mi>...,<mi>\; </mi>}{z}_{[\cdot \cdot ]}\mathrm{,}{p}_{[\cdot ]}=z_{[\cdot ]}\le z_{[\cdot \cdot ]}\mathrm{,}m\mathrm{<mi>\; </mi><mo>=</mo><mi>\; </mi>1<mi>\; </mi>}\stackrel{\text{Def}}{=}{m}_{[\cdot ]}\\ 2)z_{[\cdot ]}^{\cdot }\mathrm{,<mi>\; </mi>...,<mi>\; </mi>}{z}_{[\cdot \cdot ]}^{\cdot }\mathrm{,}{z}_{[\cdot ]}^{\cdot }\mathrm{<mi>\; </mi><mo>></mo><mi>\; </mi>}{z}_{[\cdot \cdot ]}\mathrm{,}{z}_{[\cdot \cdot ]}^{\cdot }\ge z_{[\cdot ]}^{\cdot }\mathrm{,}m=2\\ 3)z_{[\cdot ]}^{\cdot \cdot }\mathrm{,<mi>\; </mi>...,<mi>\; </mi>}{z}_{[\cdot \cdot ]}^{\cdot \cdot }\mathrm{,}{z}_{[\cdot ]}^{\cdot \cdot }\mathrm{<mi>\; </mi><mo>></mo><mi>\; </mi>}{z}_{[\cdot \cdot ]}\mathrm{,}{z}_{[\cdot \cdot ]}^{\cdot \cdot }\ge z_{[\cdot ]}^{\cdot \cdot }\mathrm{,}m=3\\ \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \\ \cdot \mathrm{...}\cdot )z_{[\cdot ]}^{\cdot \mathrm{<mi>\; </mi>...<mi>\; </mi>}\cdot }\mathrm{,<mi>\; </mi>...,<mi>\; </mi>}{z}_{[\cdot \cdot ]}^{\cdot \mathrm{<mi>\; </mi>...<mi>\; </mi>}\cdot }\mathrm{,}{p}_{[\cdot \cdot ]}=z_{[\cdot \cdot ]}^{\cdot \mathrm{<mi>\; </mi>...<mi>\; </mi>}\cdot }\ge z_{[\cdot ]}^{\cdot \mathrm{<mi>\; </mi>...<mi>\; </mi>}\cdot }\mathrm{,}m=\cdot \mathrm{<mi>\; </mi>...<mi>\; </mi>}\cdot \stackrel{\text{Def}}{=}{m}_{[\cdot \cdot ]}\end{array}$$E64

(the first of them is considered only).

The situation in the first block is described only by (64).

$${✠}^6$$ We check whether, by this way, two new identical successive blocks of unique six-partite structures are created $$[$$ the first block is between the (newly numbered) rows $$m_{[\cdot ]}÷m_{[\cdot \cdot ]}$$ and the second is (newly) between the rows $$m_{[\cdot \cdot ]}÷m_{[\cdot \cdot \cdot ]}]$$.

Their lengths are $$\mathrm{\Delta }{m}_{[\cdot ]}$$ and $$\mathrm{\Delta }{m}_{[\cdot \cdot ]}$$ $$[$$ for $$\mathrm{\Delta }{m}_{[\cdot \cdot ]}:$$ $$m_{[\cdot \cdot ]}:=(m_{[\cdot \cdot ]}{)}_{\text{mod}(m_{[\cdot \cdot ]}-1)}]$$,

$$\mathrm{\Delta }{m}_{[\cdot ]}=m_{[\cdot \cdot ]}-m_{[\cdot ]}+1\le \mathrm{\Delta }{p}_{[\cdot ]}\mathrm{,}\mathrm{\Delta }{m}_{[\cdot \cdot ]}=m_{[\cdot \cdot \cdot ]}-m_{[\cdot \cdot ]}+1\le \mathrm{\Delta }{p}_{[\cdot \cdot ]}\mathrm{.}$$E65

If NOT - we continue with $${✠}^2$$, $$p*=p_{[\mathrm{...}]}$$ ; $${✠}^1$$ when $$e\cdot P$$ is exhausted, $$e:=e+1$$ ;

If YES - the distances ($$\mathrm{\Delta }{m}_{[\cdot ]}[-2]$$ and $$\mathrm{\Delta }{m}_{[\cdot \cdot ]}[-2]$$) between the marginal rows of the new blocks ($${✠}^5$$) are constant, $$\mathrm{\Delta }{m}_{[\cdot ]}=\mathrm{\Delta }{m}_{[\cdot \cdot ]}$$,

[the distances are counted in the number $$m$$ of the unique six-partite structures ($${✠}^5$$), the last one of the first block is the first one of the second block], $$\mathrm{\Delta }{m}_{[\cdot ]}=\mathrm{\Delta }{m}_{[\cdot \cdot ]}$$.

$${✠}^7$$ If the distance $$\mathrm{\Delta }{p}_{[\cdot ]}$$ of the first and the last row of the first block ($${✠}^2$$) is less or equal to the distance $$\mathrm{\Delta }{p}_{[\cdot \cdot ]}$$ of the first and last row of the second blok $$\mathrm{\Delta }{p}_{[\cdot ]}\le \mathrm{\Delta }{p}_{[\cdot \cdot ]}$$, we have discovered the infinite cycle driven by the program $$\overrightarrow{\eta }$$ [now the distances are counted in the number of steps $$p$$].

We continue further but within the first block and with the $$\mathrm{\Delta }{m}_{[\cdot ]}$$ only.

From each unique six-partite structures ($${✠}^5$$, $${✠}^6$$) the three columns

$$\left[q\parallel G\parallel m\right]$$E66

are now taken only, being interpreted as the rules of a regular grammar (accepted by a finite automaton)

$$\begin{array}{c}{S}_{q*}\to G_m{S}_{q_m}\\ q*\in \left\{0\right\}\stackrel{\mathrm{.}}{\cup }\left\{\mathrm{1,<mi>\; </mi>...,<mi>\; </mi><mo>|</mo>}\overrightarrow{\eta }|\right\}\mathrm{,}{q}_m\in \left\{\mathrm{1,<mi>\; </mi>...,<mi>\; </mi><mo>|</mo>}\overrightarrow{\eta }|\right\}\mathrm{,<mi>\; </mi><mi>\; </mi><mi>\; </mi>}m=m_{[\cdot ]}\mathrm{,<mi>\; </mi>...,<mi>\; </mi>}{m}_{[\cdot \cdot ]}-1\end{array}$$E67

with the set $$S$$ of nonterminal symbols and the set $$T^{\prime }$$ of terminal symbols,

$$S_{*}\stackrel{\text{Def}}{=}\left\{S_0\right\}\stackrel{\mathrm{.}}{\cup }{\left\{S_{q_{m_{}}}\right\}}_{m=m_{[\cdot ]}}^{m_{[\cdot \cdot ]}-1}\mathrm{,<mi>\; </mi><mi>\; </mi><mi>\; </mi>}\text{card}{S}_{*}=n\mathrm{,<mi>\; </mi><mi>\; </mi><mi>\; </mi>}{T}^{\prime }\stackrel{\text{Def}}{=}{\left\{G_{q_{m_{}}}\right\}}_{m=m_{[\cdot ]}}^{m_{[\cdot \cdot ]}-1}$$E68

having the starting nonterminal symbol $$S_0\in S$$.

$${✠}^{7a}$$ If the distance $$\mathrm{\Delta }{p}_{[\cdot ]}$$ of the first and the last row of the first block ($${✠}^5$$ is greater than the distance $$\mathrm{\Delta }{p}_{[\cdot \cdot ]}$$ of the first and last row of the second blok, $$\mathrm{\Delta }{p}_{[\cdot ]}>\mathrm{\Delta }{p}_{[\cdot \cdot ]}$$, we have discovered the finite cycle driven by the program $$\overrightarrow{\eta }$$.

$${✠}^8$$ For the first block of the unique six–partite structures ($${✠}^5$$, $${✠}^6$$, $${✠}^7$$) the sequence of rules of a regular grammar is being generated (accepted by the finite automaton with the states $$S_0\mathrm{,}{S}_{q_{m_{[\cdot ]}}}\mathrm{,}\dots$$)

$$\begin{array}{lll}{S}_0\hfill & \to \hfill & G_{m_{[\cdot ]}}{S}_{q_{m_{[\cdot ]}}}\hfill \\ S_{q_{m_{[\cdot ]}}}\hfill & \to \hfill & G_{m_{[\cdot ]}+1}{S}_{q_{m_{[\cdot ]}+1}}\hfill \\ \cdots \hfill & \cdots \hfill & \cdots \hfill \\ S_{q_{m_{[\cdot \cdot ]}-2}}\hfill & \to \hfill & G_{m_{[\cdot \cdot ]}-1}{S}_{q_{m_{[\cdot \cdot ]}-1}}\hfill \\ S_{q_{m_{[\cdot \cdot ]}-2}}\hfill & \to \hfill & \overrightarrow{\epsilon }{S}_0\mathrm{,}\left[\mathrm{or}{S}_{q_{m_{[\cdot \cdot ]}-1}}\to \epsilon S_{HALT}\mathrm{,}{S}_{HALT}\notin S\right]\hfill \end{array}$$E69

where the denotation $$S_{q_{m_{[\cdot ]}}}\triangleq S_{z_{[\cdot ]},\dots ,z_{[\cdot \cdot ]}}\mathrm{,}{S}_{q_{m_{[\cdot ]}}+1}\triangleq S_{z_{[\cdot ]}^{\cdot },\dots ,z_{[\cdot \cdot ]}^{\cdot }}\mathrm{,}\dots S_{q_{m_{[\cdot \cdot ]}}}\triangleq S_{z_{[\cdot ]}^{\cdot \mathrm{<mi>\; </mi>...<mi>\; </mi>}\cdot },\dots ,z_{[\cdot \cdot ]}^{\cdot \mathrm{<mi>\; </mi>...<mi>\; </mi>}\cdot }}$$ is used.

We have described the activity of a finite automaton which accepts the infinite regular language of the general configurations types (of the configurations of the observed machine $$TM$$). They are the words of the infinite length and having the form

$${\left[{\left({\overrightarrow{\sigma }}_m\mathrm{,}{s}_m\mathrm{,}{\overrightarrow{\rho }}_m\right)}_{m=m_{[\cdot ]}}^{m_{[\cdot \cdot ]}-1}\right]}^{+}={\left[\overrightarrow{X}\right]}^{+}\mathrm{<mi>\; </mi><mi>\; </mi><mi>\; </mi>}\left[\triangleq {\left[d(T{M}^{*})\right]}^{+}\right]$$E70

Yet after the second round of the observed $$TM$$ through the infinite cycle has been finished the Pumping Lemma is usable and valid for the length $$L$$ of the relevant word of this infinite language, $$\text{[card}S\le L<2\cdot \text{card}S]$$.

We can generate the status (the signal) $$S_{HALT}$$ to halt the whole machine $$OTM$$ and the $$TM$$ consequently.

We can say, briefly, that: If such the three identical bi-partite structures $$\left[{\eta }_{}\mathrm{,}(\overrightarrow{\sigma }\mathrm{,}s\mathrm{,}\overrightarrow{\rho })\right]$$, following each other, exist that for their distances $$\mathrm{\Delta }{p}_{[\cdot ]}$$ (measured by the number of steps of the observed process) between the first and the second bi-partite structure and $$\mathrm{\Delta }{p}_{[\cdot \cdot ]}$$ between the second and the third bi-partite structure it is valid that $$\mathrm{\Delta }{p}_{[\cdot ]}\le \mathrm{\Delta }{p}_{[\cdot \cdot ]}$$, the observed $$TM$$ is going through the infinite cycle.

The expression (70) means that we have discovered, within the dynamical system $$O{O}^{″}$$, the dynamical subsystem $$O^{*}{O}^{*}{}^{\prime }$$ ($$\equiv T{M}^{*}$$) which is in a limit cycle. It means the thermodynamic equilibrium within the double cycle $$O^{*}{O}^{*}{}^{\prime }$$, thus for its temperatures it is valid that $$T^{*}{}_W=T^{*}{\text{'}}_W$$, $$T^{*}{}_0=T^{*}{\text{'}}_0$$ ; for sequences of the general configuration types ($$G_{[\cdot ]}$$), $$\overrightarrow{X_p}$$ and $$\overrightarrow{X_{p+1}}$$ from (59), (60), it is valid, for certain $$p\ge p^{*}\ge p^0\ge 1$$, that

$$\begin{array}{l}H\left(\overrightarrow{X_p}\right)-H\left(\overrightarrow{X_p}|\overrightarrow{X_{p+1}}\right)=0\mathrm{where}\\ \overrightarrow{X_p}=\left(X_{p+1}\mathrm{,<mi>\; </mi>...,<mi>\; </mi>}{X}_{2p+2-p*}\right)=\left(X_{p*}\mathrm{,<mi>\; </mi>...,<mi>\; </mi>}{X}_p\right)\end{array}$$E71

which represents the zero change of the information and thermodynamic entropy within the working medium of a reversible Carnot Cycle; for the sequences $$\overrightarrow{X_p}$$ and $$\overrightarrow{X_{p+1}}$$ of the observed $$TM$$ ’s configurations $$X_{[\cdot ]}$$ from (47) ($$TM\equiv O$$) it is valid that

$$H(\overrightarrow{X_p})-H\left(\overrightarrow{X_p}|\overrightarrow{X_{p+1}}\right)=H(\overrightarrow{Y_p}\mathrm{<mo\; stretchy="false">)</mo><mo>></mo>0,<mi>\; </mi><mi>\; </mi>}\overrightarrow{X_{[\cdot ]}}\triangleq X_{p_{*}}\mathrm{,<mi>\; </mi>...,<mi>\; </mi>}{X}_{[\cdot ]}\mathrm{,}{p}^{*}\ge 1$$E72

which represents the nonzero output and, also, the growth of the thermodynamic and information entropy within the whole isolated system in which that reversible Carnot Cycle is running, see [6, 8]. Generally, any Carnot Cycle is, under its construction draft, the infinite cycle, and, thus, both the relations (71) and (72) represent the information thermodynamic criterion for the infinite cycle existence.

The following section gives the examples of this method.

6. Examples

Example I

$$\begin{array}{l}\overrightarrow{\eta }=\left({\eta }_1\mathrm{,}{\eta }_2\mathrm{,}{\eta }_3\mathrm{,}{\eta }_4\right);\\ {\eta }_1=\left(s_0\mathrm{,}I\mathrm{,}{s}_0\mathrm{,}I\mathrm{,}R\right)\\ {\eta }_2=\left(s_0\mathrm{,}B\mathrm{,}{s}_1\mathrm{,}I\mathrm{,}L\right)\\ {\eta }_3=\left(s_1\mathrm{,}I\mathrm{,}{s}_1\mathrm{,}I\mathrm{,}L\right)\\ {\eta }_4=\left(s_1\mathrm{,}B\mathrm{,}{s}_0\mathrm{,}B\mathrm{,}R\right)\end{array}$$E73

This program conserves the given string $$\overrightarrow{\xi }$$

$$\overrightarrow{\xi }=\left[IIII\mathrm{...}I\right]\mathrm{resp}\mathrm{.}B\left[IIII\mathrm{...}I\right]B\mathrm{resp}\mathrm{.}B\left[IIII\mathrm{...}I\right]B$$E74

or $$B\overrightarrow{I}B$$ respectively. Let the input $$\overrightarrow{\xi }=IIIII$$ be given. From the table Tab. 1 it is obvious that

$$\begin{array}{l}{p}_{[\cdot ]}\mathrm{<mo>=</mo>1,<mi>\; </mi><mi>\; </mi>}{p}_{[\cdot \cdot ]}\mathrm{<mo>=</mo>13,<mi>\; </mi><mi>\; </mi>}{p}_{[\cdot \cdot \cdot ]}\mathrm{<mo>=</mo>25,<mi>\; </mi><mi>\; </mi>}{m}_{[\cdot ]}\mathrm{<mo>=</mo>1,<mi>\; </mi><mi>\; </mi>}{m}_{[\cdot \cdot ]}=7and\mathrm{thus}\\ \mathrm{\Delta }{p}_{[\cdot ]}\mathrm{<mo>=</mo>11,<mi>\; </mi><mi>\; </mi>}\mathrm{\Delta }{p}_{[\cdot \cdot ]}\mathrm{<mo>=</mo>13,<mi>\; </mi><mi>\; </mi>}\mathrm{\Delta }{p}_{[\cdot \cdot \cdot ]}\mathrm{<mo>=</mo>15,<mi>\; </mi><mi>\; </mi>}\mathrm{\Delta }{m}_{[\cdot ]}=\mathrm{\Delta }{m}_{[\cdot \cdot ]}=\mathrm{\Delta }{m}_{[\cdot \cdot \cdot ]}\mathrm{<mo>=</mo><mi>\; </mi>...<mi>\; </mi><mo>=</mo>7}\end{array}$$E75

Then we can write down the regular grammar of the (regular) language of the general configuration given by the computing process driven by the program $$\overrightarrow{\eta }$$,

$$\begin{array}{l}{S}_0\to \overrightarrow{B}{s}_0\overrightarrow{IB}{S}_1\\ S_1\to \overrightarrow{BI}{s}_0\overrightarrow{IB}{S}_{\mathrm{2<mi>\; </mi>3<mi>\; </mi>4<mi>\; </mi>5}}\\ S_{\mathrm{2<mi>\; </mi>3<mi>\; </mi>4<mi>\; </mi>5}}\to \overrightarrow{BI}{s}_0\overrightarrow{B}{S}_6\\ S_6\to \overrightarrow{BI}{s}_1\overrightarrow{IB}{S}_{\mathrm{7<mi>\; </mi>8<mi>\; </mi>9<mi>\; </mi>10}}\\ S_{\mathrm{7<mi>\; </mi>8<mi>\; </mi>9<mi>\; </mi>10}}\to \overrightarrow{B}{s}_1\overrightarrow{IB}{S}_{11}\\ S_{11}\to \overrightarrow{B}{s}_1\overrightarrow{BIB}{S}_{12}\\ S_{12}\to \overrightarrow{\epsilon }{S}_0\end{array}$$E76

This grammar is with the set $S_{\ast }$ of its nonterminal symbols,

$$S_{\ast }=\left\{S_0{S}_1{S}_{\mathrm{2<mi>\; </mi>3<mi>\; </mi>4<mi>\; </mi>5}}{S}_6{S}_{\mathrm{7<mi>\; </mi>8<mi>\; </mi>9<mi>\; </mi>10}}{S}_{11}{S}_{12}\right\}\mathrm{,}\text{card }{S}_{\ast }=7$$E77

(let us remember (66)-(69) and that $$S_1\triangleq S_{q_1}$$, $$S_{\mathrm{2<mi>\; </mi>3<mi>\; </mi>4<mi>\; </mi>5}}\triangleq S_{q_2}$$, $$S_6\triangleq S_{q_3}$$, $$S_{\mathrm{7<mi>\; </mi>8<mi>\; </mi>9<mi>\; </mi>10}}\triangleq S_{q_4}$$, $$S_{11}\triangleq S_{q_5}$$, $$S_{12}=S_{q_6}$$)

and generates (the computing process described by it generates) the infinite word $${\left[\overrightarrow{X}\right]}^{+}$$,

$${\left[\overrightarrow{X}\right]}^{+}={\left[\overrightarrow{B}{s}_0\overrightarrow{IB}\mathrm{,}\overrightarrow{BI}{s}_0\overrightarrow{IB}\mathrm{,}\overrightarrow{BI}{s}_0\overrightarrow{B}\mathrm{,}\overrightarrow{BI}{s}_1\overrightarrow{IB}\mathrm{,}\overrightarrow{B}{s}_1\overrightarrow{IB}\mathrm{,}\overrightarrow{B}{s}_1\overrightarrow{BIB}\right]}^{+}={\left[d(T{M}^{*})\right]}^{+}$$E78

For the generation of the signal which halts the whole combined machine we can add and use the rule

$$S_{12}\to \epsilon S_{HALT}\mathrm{,}{S}_{HALT}\notin S_{*}$$E79

After the second round through the indicated infinite cycle the word of the general configuration types of the length l=12 is generated out and, thus, the Pumping Lemma it is valid,

$$\begin{array}{l}\text{card }{S}_{*}\le l<2\cdot (\text{card }{S}_{*})\mathrm{,}\text{card }{S}_{*}=7\\ 7\le \mathrm{<mi>\; </mi>12<mi>\; </mi><mo><</mo>2}\cdot 7\end{array}$$E80

See the following table.

Table 1.

Tracing and staging for Example I

[We ’idle’ for the same number of clicks $$\mathrm{\Delta }p$$ in each of the blocks $$\mathrm{\Delta }m$$. The sequence of $$\mathrm{\Delta }p$$ is $$\left(11,11,11,\dots \right)$$, the sequence of $$\mathrm{\Delta }m$$ is $$\left(5,5,5,\dots \right)$$. The sequence for $$p$$ is $$\left(13,13,13,\dots \right)$$ and for $$m$$ is $$\left(7,7,7,\dots \right)$$.]

After the observed (sub)machine has entered into the infinite cycle, which takes place in a finite time, and has gone through this cycle twice it is halted by the signal from the observing machine.

Example II

$$\begin{array}{l}\overrightarrow{\eta }=\left({\eta }_1\mathrm{,}{\eta }_2\mathrm{,}{\eta }_3\mathrm{,}{\eta }_4\right)\\ {\eta }_1=\left(s_0\mathrm{,}I\mathrm{,}{s}_0\mathrm{,}I\mathrm{,}R\right)\\ {\eta }_2=\left(s_0\mathrm{,}B\mathrm{,}{s}_1\mathrm{,}I\mathrm{,}L\right)\\ {\eta }_3=\left(s_1\mathrm{,}I\mathrm{,}{s}_1\mathrm{,}I\mathrm{,}L\right)\\ {\eta }_4=\left(s_1\mathrm{,}B\mathrm{,}{s}_0\mathrm{,}B\mathrm{,}R\right)\end{array}$$E81

This program generates the expanding sequence

$$\left[IIIII\right]resp\mathrm{.}B\left[IIIII\mathrm{...}I\right]B\mathrm{,}\dots \mathrm{,}B\left[IIII\mathrm{...}I\mathrm{...}\right]B\mathrm{,}\dots$$E82

or $$B\overrightarrow{I}B$$ respectively. Let the input $$\overrightarrow{\xi }=IIIII$$ be given. From the following table Tab. 2 it is obvious that

$$\begin{array}{l}{p}_{[\cdot ]}\mathrm{<mo>=</mo>1,<mi>\; </mi><mi>\; </mi>}{p}_{[\cdot \cdot ]}\mathrm{<mo>=</mo>13,<mi>\; </mi><mi>\; </mi>}{p}_{[\cdot \cdot \cdot ]}\mathrm{<mo>=</mo>27,<mi>\; </mi><mi>\; </mi>}{m}_{[\cdot ]}\mathrm{<mo>=</mo>1,<mi>\; </mi><mi>\; </mi>}{m}_{[\cdot \cdot ]}=7\mathrm{and}\mathrm{thus}\\ \mathrm{\Delta }{p}_{[\cdot ]}\mathrm{<mo>=</mo>11,<mi>\; </mi><mi>\; </mi>}\mathrm{\Delta }{p}_{[\cdot \cdot ]}\mathrm{<mo>=</mo>13,<mi>\; </mi><mi>\; </mi>}\mathrm{\Delta }{p}_{[\cdot \cdot \cdot ]}\mathrm{<mo>=</mo>15,<mi>\; </mi><mi>\; </mi>}\mathrm{\Delta }{m}_{[\cdot ]}=\mathrm{\Delta }{m}_{[\cdot \cdot ]}=\mathrm{\Delta }{m}_{[\cdot \cdot \cdot ]}\mathrm{<mo>=</mo><mi>\; </mi>...<mi>\; </mi><mo>=</mo>7}\end{array}$$E83

and we can write down the regular grammar (of the regular) language of the general configuration types generated by the computing process driven by $$\overrightarrow{\eta }$$

$$\begin{array}{c}{S}_0\to \overrightarrow{B}{s}_0\overrightarrow{IB}{S}_1\\ S_1\to \overrightarrow{BI}{s}_0\overrightarrow{IB}{S}_{\mathrm{2<mi>\; </mi>3<mi>\; </mi>4<mi>\; </mi>5}}\\ S_{\mathrm{2<mi>\; </mi>3<mi>\; </mi>4<mi>\; </mi>5}}\to \overrightarrow{BI}{s}_0\overrightarrow{B}{S}_6\\ S_6\to \overrightarrow{BI}{s}_1\overrightarrow{IB}{S}_{\mathrm{7<mi>\; </mi>8<mi>\; </mi>9<mi>\; </mi>10}}\\ S_{\mathrm{7<mi>\; </mi>8<mi>\; </mi>9<mi>\; </mi>10}}\to \overrightarrow{B}{s}_1\overrightarrow{IB}{S}_{11}\\ S_{11}\to \overrightarrow{B}{s}_1\overrightarrow{BIB}{S}_{12}\\ S_{12}\to \overrightarrow{\epsilon }{S}_0\end{array}$$E84

where, after the relations (66)-(69), $$S_1\triangleq S_{q_1}$$, $$S_{\mathrm{2<mi>\; </mi>3<mi>\; </mi>4<mi>\; </mi>5}}\triangleq S_{q_2}$$, $$S_6\triangleq S_{q_3}$$, $$S_{\mathrm{7<mi>\; </mi>8<mi>\; </mi>9<mi>\; </mi>10}}\triangleq S_{q_4}$$, $$S_{11}\triangleq S_{q_5}$$, $$S_{12}=S_{q_6}$$.

This grammar is with the set of nonterminal symbols

$$S_{*}=\{S_0{S}_1{S}_{\mathrm{2<mi>\; </mi>3<mi>\; </mi>4<mi>\; </mi>5}}{S}_6{S}_{\mathrm{7<mi>\; </mi>8<mi>\; </mi>9<mi>\; </mi>10}}{S}_{11}{S}_{12}\mathrm{<mo>\}</mo>,<mi>\; </mi><mi>\; </mi>}\text{card }{S}_{*}=7$$E85

and generates (the computing process described by it generates) the infinite word $${\left[\overrightarrow{X}\right]}^{+}$$,

$${\left[\overrightarrow{X}\right]}^{+}={\left[\overrightarrow{B}{s}_0\overrightarrow{IB}\mathrm{,}\overrightarrow{BI}{s}_0\overrightarrow{IB}\mathrm{,}\overrightarrow{BI}{s}_0\overrightarrow{B}\mathrm{,}\overrightarrow{BI}{s}_1\overrightarrow{IB}\mathrm{,}\overrightarrow{B}{s}_1\overrightarrow{IB}\mathrm{,}\overrightarrow{B}{s}_1\overrightarrow{BIB}\right]}^{+}={\left[d(T{M}^{*})\right]}^{+}$$E86

For the generation of the signal which halts the whole combined machine we can add and use the rule

$$S_{12}\to \epsilon S_{HALT}\mathrm{,}{S}_{HALT}\notin S_{*}$$E87

After the second round through the indicated infinite cycle the word of the general configuration types of the length $$l=12$$ is generated and, thus, the Pumping Lemma it is valid,

$$\begin{array}{l}\text{card }{S}_{*}\le l<2\cdot (\text{card }{S}_{*})\mathrm{,}\text{card }{S}_{*}=7\\ 7\le \mathrm{<mi>\; </mi>12<mi>\; </mi><mo><</mo>2}\cdot 7\end{array}$$E88

See the following table.

We are going through the seven states repeatedly and each such a pass lasts longer than the previous one.

We ’idle’ in such each pass a longer time (for the growing number of clicks $$p$$ of the $C{U}_{TM}$).

[The growing sequence of $$\mathrm{\Delta }p$$ is (11, 13, 15,...) is evidenced while the sequence of $$\mathrm{\Delta }m$$ is (5,5,5,...).

The sequence for $$p$$ is (13, 15, 17,...) and for $$m$$ is (7, 7, 7,...).]

After the observed (sub)machine has entered into the infinite cycle, which occurs in a finite time, and has gone through this cycle twice it is halted by the signal from the observing machine.

Table 2.

Tracing and staging for Example II

Example III

$$\begin{array}{l}\overrightarrow{\eta }=\left({\eta }_1\mathrm{,}{\eta }_2\mathrm{,}{\eta }_3\mathrm{,}{\eta }_4,{\eta }_5\mathrm{,}{\eta }_6\mathrm{,}{\eta }_7{\eta }_8\mathrm{,}{\eta }_9\mathrm{,}{\eta }_{10}{\eta }_{11}\mathrm{,}{\eta }_{12}\mathrm{,}{\eta }_{13}\right)\\ {\eta }_1=\left(s_0\mathrm{,}I\mathrm{,}{s}_1\mathrm{,}B\mathrm{,}R\right)\\ {\eta }_2=\left(s_1\mathrm{,}I\mathrm{,}{s}_1\mathrm{,}I\mathrm{,}R\right)\\ {\eta }_3=\left(s_1\mathrm{,}B\mathrm{,}{s}_2\mathrm{,}B\mathrm{,}R\right)\\ {\eta }_4=\left(s_2\mathrm{,}I\mathrm{,}{s}_2\mathrm{,}I\mathrm{,}R\right)\\ {\eta }_5=\left(s_2\mathrm{,}B\mathrm{,}{s}_3\mathrm{,}B\mathrm{,}L\right)\\ {\eta }_6=\left(s_3\mathrm{,}I\mathrm{,}{s}_4\mathrm{,}B\mathrm{,}L\right)\\ {\eta }_7=\left(s_4\mathrm{,}B\text{}\mathrm{,}{s}_H\mathrm{,}B\mathrm{,}R\right)\\ {\eta }_8=\left(s_4\mathrm{,}I\mathrm{,}{s}_5\mathrm{,}I\mathrm{,}L\right)\\ {\eta }_9=\left(s_5\mathrm{,}I\mathrm{,}{s}_5\mathrm{,}I\mathrm{,}L\right)\\ {\eta }_{10}=\left(s_5\mathrm{,}B\mathrm{,}{s}_6\mathrm{,}B\mathrm{,}L\right)\\ {\eta }_{11}=\left(s_6\mathrm{,}I\mathrm{,}{s}_6\mathrm{,}I\mathrm{,}L\right)\\ {\eta }_{12}=\left(s_6\mathrm{,}B\mathrm{,}{s}_0\mathrm{,}B\mathrm{,}R\right)\\ {\eta }_{13}=\left(s_0\mathrm{,}B\mathrm{,}{s}_0\mathrm{,}B\mathrm{,}L\right)\end{array}$$E89

This program generates, or is figuring, the difference between the numbers 3 and 4 in this order,

$3-4$E90

and without checking the negativity of the result. Thus it enters into the infinite cycle in which generates the left-direction expanding sequence

$\left[\mathrm{...}BBB\mathrm{...}BIBBB\right]\mathrm{resp}.B\left[\mathrm{...}BBB\mathrm{...}BIBBB\right]B\triangleq \overrightarrow{BIB}$E91

Let now the input word $$\overrightarrow{\xi }=IIIBIIII$$ be given.

From the following table Tab 3. it is obvious that after the generation of the finite length’s beginning part G, but of the infinite lengthy word of the general configurations numbered by values of $$m$$,

$\begin{array}{lllllllllllllllll}G=[\hfill & 1\hfill & 2\hfill & 3\hfill & 4\hfill & 5\hfill & 6\hfill & 7\hfill & 8\hfill & 9\hfill & 10\hfill & 11\hfill & 12\hfill & 13\hfill & 14\hfill & 15\hfill & 16\hfill \\ \hfill & 1\hfill & 2\hfill & 3\hfill & 5\hfill & 6\hfill & 7\hfill & 8\hfill & 10\hfill & 12\hfill & 13\hfill & 15\hfill & 16\hfill & \hfill & \hfill & \hfill & \hfill \\ \hfill & 1\hfill & 17\hfill & 18\hfill & 6\hfill & 8\hfill & 19\hfill & 20\hfill & 21\hfill & ]\hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \hfill & \hfill \end{array}$E92

the part [22]⁺ follows. From the table it is obvious that the cycle is with the values

$$\begin{array}{l}{p}_{[\cdot ]}\mathrm{<mo>=</mo>41,<mi>\; </mi><mi>\; </mi>}{p}_{[\cdot \cdot ]}\mathrm{<mo>=</mo>42,<mi>\; </mi><mi>\; </mi>}{p}_{[\cdot \cdot \cdot ]}=43\\ m_{[\cdot ]}\mathrm{<mo>=</mo>41,<mi>\; </mi><mi>\; </mi>}{m}_{[\cdot \cdot ]}=42\end{array}$$E93

We can write down the regular grammar (of the regular) language of the general configuration types generated by the computing process driven by $$\overrightarrow{\eta }$$

$$\begin{array}{c}{S}_0\to G{S}_{1\cdots 40}\\ S_{1\cdots 40}\to \overrightarrow{B}{s}_0\overrightarrow{BIB}{S}_{\mathrm{41<mi>\; </mi>42<mi>\; </mi>43}\cdots }\\ S_{\mathrm{41<mi>\; </mi>42<mi>\; </mi>43}\cdots }\to \overrightarrow{B}{s}_0\overrightarrow{BIB}{S}_{\mathrm{41<mi>\; </mi>42<mi>\; </mi>43}\cdots }\end{array}$$E94

This grammar is with the set of nonterminal symbols

$$S_{\ast }=\left\{S_0{S}_{1\cdots 40}{S}_{\mathrm{41<mi>\; </mi>42<mi>\; </mi>43}\cdots }{S}_6{S}_{\mathrm{7<mi>\; </mi>8<mi>\; </mi>9<mi>\; </mi>10}}{S}_{11}{S}_{12}\right\}\mathrm{,}\text{card }{S}_{\ast }=3$$E95

and generates the infinite word

$\left[G{\left[22\right]}^{+}\right]$E96

After the second round through the indicated infinite cycle the subword of the length l = 12 is generated out,

$$\left[\overrightarrow{B}{s}_0\overrightarrow{BIB},\overrightarrow{B}{s}_0\overrightarrow{BIB},\overrightarrow{B}{s}_0\overrightarrow{BIB}\right]$$E97

and thus, the Pumping Lemma it is valid,

$$\begin{array}{l}\text{card }{S}_{*}\le l<2\cdot (\text{card }{S}_{*})\mathrm{,}\text{card }{S}_{*}=3\\ 3\le \mathrm{<mi>\; </mi>3<mi>\; </mi><mo><</mo>2}\cdot 3\end{array}$$E98

For the generation of the signal which halts the whole combined machine we can use (or add) the rule

$$S_{414243\cdots }\to \epsilon S_{HALT}\mathrm{,}{S}_{HALT}\notin S_{\ast }$$E99

Here again it is valid that for the finite number of tracing steps and, for each is lasting the finitely long time, both halt states of our double-Turing Machine, which is the Turing Machine, too, occur in a finite time.

Table 3.

Tracing and staging for Example III

[The distance $$\mathrm{\Delta }p$$ of $$p$$ for the general configuration numbered 22 is constant $$(\mathrm{\Delta }p=0)$$.]

Example IV

$$\begin{array}{l}\overrightarrow{\eta }=\left({\eta }_1\mathrm{,}{\eta }_2\mathrm{,}{\eta }_3\mathrm{,}{\eta }_4,{\eta }_5\mathrm{,}{\eta }_6\mathrm{,}{\eta }_7{\eta }_8\mathrm{,}{\eta }_9\mathrm{,}{\eta }_{10}{\eta }_{11}\mathrm{,}{\eta }_{12}\mathrm{,}{\eta }_{13}\right)\\ {\eta }_1=\left(s_0\mathrm{,}I\mathrm{,}{s}_1\mathrm{,}B\mathrm{,}R\right)\\ {\eta }_2=\left(s_1\mathrm{,}I\mathrm{,}{s}_1\mathrm{,}I\mathrm{,}R\right)\\ {\eta }_3=\left(s_1\mathrm{,}B\mathrm{,}{s}_2\mathrm{,}B\mathrm{,}R\right)\\ {\eta }_4=\left(s_2\mathrm{,}I\mathrm{,}{s}_2\mathrm{,}I\mathrm{,}R\right)\\ {\eta }_5=\left(s_2\mathrm{,}B\mathrm{,}{s}_3\mathrm{,}B\mathrm{,}L\right)\end{array}$$E100

$$\begin{array}{l}{\eta }_6=\left(s_3\mathrm{,}I\mathrm{,}{s}_4\mathrm{,}B\mathrm{,}L\right)\\ {\eta }_7=\left(s_4\mathrm{,}B\text{}\mathrm{,}{s}_H\mathrm{,}B\mathrm{,}R\right)\\ {\eta }_8=\left(s_4\mathrm{,}I\mathrm{,}{s}_5\mathrm{,}I\mathrm{,}L\right)\\ {\eta }_9=\left(s_5\mathrm{,}I\mathrm{,}{s}_5\mathrm{,}I\mathrm{,}L\right)\\ {\eta }_{10}=\left(s_5\mathrm{,}B\mathrm{,}{s}_6\mathrm{,}B\mathrm{,}L\right)\\ {\eta }_{11}=\left(s_6\mathrm{,}I\mathrm{,}{s}_6\mathrm{,}I\mathrm{,}L\right)\\ {\eta }_{12}=\left(s_6\mathrm{,}B\mathrm{,}{s}_0\mathrm{,}B\mathrm{,}R\right)\\ {\eta }_{13}=\left(s_0\mathrm{,}B\mathrm{,}{s}_0\mathrm{,}B\mathrm{,}L\right)\end{array}$$BB0

This program is figuring the difference 4-3 and the input is $$\overrightarrow{\xi }=IIIBIIII$$.

From the following table follows that during our staging the whole double-machine halts itself. In the numbers $$m$$ of the general configuration types the following word G is generated,

$\begin{array}{l}G=\left[G_1{G}_2\right],l=2\\ G_1=\left[123456789101112\right]\\ G_2=\left[123513141516\right]\end{array}$E101

We can write the regular grammar of the (regular) language of the general configuration types being generated by the process driven by $$\overrightarrow{\eta }$$,

$$\begin{array}{c}{S}_0\to G_1{S}_{12345678910111213}\\ S_{12345678910111213}\to G_2{S}_{1415161718192021}\end{array}$$E102

This grammar has the set $S_{\ast }$ of the nonterminal symbols,

$$S_{\ast }=\left\{S_0{S}_{12345678910111213}{S}_{1415161718192021}\equiv S_{HALT}\right\}\mathrm{,}\text{card }{S}_{\ast }=3$$E103

The whole staging is ended by the natural end of the process in the observed machine.

Table 4.

Tracing and staging for Example IV

[All computing and tracing is stopped by the end of the observed process.]

All the previous examples have shown that after the finite number of steps, each is interpreted in a finite time and thus we need the finite time only, the signal halting the whole double machine is generated in the all cases. The reason for generating the halting signal and as such, the recognition the finite or infinite cycle in the observed machine is quite visible from all our tracing tables. Our double machine is the Turing Machine, too.

7. Conclusion

The unsolvable decision problems are of two types. The first type of the problem is solvable but not with the objects and decision-counting methods we have at our disposal. The example is the unsolvability of the binomical equations in the real axis. But with the Complex Numbers Theory they are solvable describing the physical reality. The help is that the imaginary axis (the new dimension) has been introduced. The another example is the Great Fermat Theorem and its solution (Andrew Wiles 1993 and Ann. Math. 1995).

The second type of the unsolvable or undecidable problems are those which are given mistakenly by having an Auto-Reference embedded. They are the paradoxes, which invokes the infinite cycles when they are ’solved’ and just for this they are reducible to the Halting Problem; their solution without a certain ’step-aside’ requires the Perpetuum Mobile functionality. This doesn’t mean that a counting under their description is not performed physically but is not resultative in a finite time.

(Nevertheless we can want to have the infinite cycle for technology purposes, e.g. the push-pull circuit. Here the infinite cycle’s functionality is created intentionally and, as such, the push-pull circuit is the example of the recurring but not recursive counting. Here the Auto-Reference is introduced intentionally, as a successive figuring method, creating an infinite sequence of wanted values.)

Generally, a sequence of states or figuring steps of solving a problem could be divergent or constant or convergent. The divergent and constant cases are felt as the real example of the infinite cycle in the very sense of this term. We can say, rather jokingly, that the convergent counting halts, even if it was in the infinity (e.g. the Newton method) and that the divergent counting doesn’t halt even in the infinity, including now the constant sequence too - the model is the information transfer in an interrupted information transfer channel. When in the recurring counting the number of figuring steps is not given explicitly, then, the results from the successive steps must be compared. When it is set badly or is not set at all, the infinite cycle occurs and, by the algorithm’s definition requiring resultativness, such a counting is errorneous. The flagrant example of the badly set task is the way in which the Gibbs Paradox arises - here it is the Auto-Reference embedded by not respecting the difference between what is measured (observed), and what is measuring (observing). We used it in the extreme case (with the complete mixing these two levels) as the physical model of all noetic paradoxes.

The aim of this paper was to detect the infinite cycle from its own characteristics. Our vision is that the counting itself is of the physical character and, as such, is subjected to physical laws, especially, to the II Principle of Thermodynamics. The infinite cycle is viewed as a certain type of an equilibrium state.

The interesting is that the stability of an equilibrium state and of an atomic structure are similar. Without the natural radioactivity the end of atoms seems to ’be in the infinity’, too.

To await the finite-time end of such states is a paradoxical and, as such, unachievable wish. Nevertheless, all these cycles are representable by the Carnot Cycle (it is the infinite cycle conceptually) used as the thermodynamic model of a cyclic information transfer [6, 8, 10]. We see here the growth of thermodynamic entropy within the whole isolated system in which the cycle, or the information transfer, is running and we see the constant or decreasing thermodynamic entropy within its working medium, or within the transfer channel in the information-thermodynamic representation. From this point of view the aim to recognize any infinite cycle, to decide the Halting Problem, is solvable. The information-thermodynamic considerations were expressed in terms of the Automaton Theory The general configuration types of the observed Turing Machine were generated and the Pumping Lemma was used. The author believes that he has shown that problems given paradoxically, errorneously as for being resultant, have the Auto-Reference embedded both in the sense of the objective of the problem or in the sense of the solving the problem - the Auto-Reference can be in the solving method while the very objective of the problem can be solvable. The author’s wish is that the following claim could be considered as the theorem for recognizing, deciding of any infinite cycle:

Due to the fact that any infinite cycle starts at a finite time and, for the Control Unit of any Turing Machine is an finite-state automaton, and due to the fact that the Pumping Lemma it is valid for the regular infinite and thus periodical language of the general configuration types of the observed Turing Machine, the Halting Problem is decidable.

8. Appendix

We consider the basic types of chains of the terminal symbols on the input-output $$TM$$ ’s tape,

$$I\triangleq \overrightarrow{I}\mathrm{<mo>;</mo><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi>}\overrightarrow{I}=I\mathrm{,}\overrightarrow{I}=II\mathrm{,}\overrightarrow{I}=III\mathrm{...}$$

$$B\triangleq \overrightarrow{B}\mathrm{<mo>;</mo><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi>}\overrightarrow{B}=B\mathrm{,}\overrightarrow{B}=BB\mathrm{,}\overrightarrow{B}=BBB\mathrm{,<mi>\; </mi>...,<mi>\; </mi>}\underset{\_}{B\triangleq \epsilon }$$

Further types are

$$\begin{array}{l}IB\triangleq \overrightarrow{I}\overrightarrow{B};\overrightarrow{I}\overrightarrow{B}=IB\mathrm{,}\overrightarrow{I}\overrightarrow{B}=IIB\mathrm{,}\overrightarrow{I}\overrightarrow{B}=III\mathrm{...}B\\ \mathrm{<mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi>}\mathrm{<mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi>}\overrightarrow{I}\overrightarrow{B}=IBB\mathrm{,}\overrightarrow{I}\overrightarrow{B}=IBBB\mathrm{...}\\ \mathrm{<mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi>}\mathrm{<mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi>}\overrightarrow{I}\overrightarrow{B}=III\mathrm{...}BBB\mathrm{...}\end{array}$$

$$\begin{array}{l}BI\triangleq \overrightarrow{B}\overrightarrow{I};\overrightarrow{B}\overrightarrow{I}=BI\mathrm{,}\overrightarrow{B}\overrightarrow{I}=BBI\mathrm{,}\overrightarrow{B}\overrightarrow{I}=BBB\mathrm{...}I\\ \mathrm{<mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi>}\mathrm{<mi>\; </mi><mi>\; </mi><mi>\; </mi>}\overrightarrow{B}\overrightarrow{I}=BII\mathrm{,}\overrightarrow{B}\overrightarrow{I}=BIII\mathrm{...}\\ \mathrm{<mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi>}\mathrm{<mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi>}\overrightarrow{B}\overrightarrow{I}=BBB\mathrm{...}III\mathrm{...}\end{array}$$

$$IBI\triangleq \overrightarrow{I}\overrightarrow{B}\overrightarrow{I}=III\mathrm{...}BBB\mathrm{...}III\mathrm{...}I$$

$$BIB\triangleq \overrightarrow{B}\overrightarrow{I}\overrightarrow{B}=BBB\mathrm{...}III\mathrm{...}BBB\mathrm{...}B$$

$$IBB\triangleq IB$$

$$IBB\triangleq IB\mathrm{,}$$

$$IIB\triangleq IB$$

$$IIB\triangleq IB$$

$$\overrightarrow{IB}\triangleq IB\mathrm{,<mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi><mi>\; </mi>}\overrightarrow{IB}\triangleq IBIB\mathrm{...}IBIB$$

$$\overrightarrow{IB}B\triangleq IBB\mathrm{,<mi>\; </mi><mi>\; </mi><mi>\; </mi>}\overrightarrow{IB}B\triangleq IBIB\mathrm{...}IBB=IBIB\mathrm{...}IBIB=\overrightarrow{IB}$$

The following equivalences of chains of the terminal symbols are considerable,

$$\overrightarrow{IB}B\triangleq IBIB\mathrm{...}IBIBB=IBIB\mathrm{...}IBIB=\overrightarrow{IB}$$

$$\overrightarrow{IBI}\triangleq IBIIBI\mathrm{...}IBIIBI=IBIB\mathrm{...}IBI$$

$$\overrightarrow{IBI}I\triangleq \overrightarrow{IBI}$$

$$\overrightarrow{IBI}B\triangleq \overrightarrow{IB}$$

$$\overrightarrow{I\overrightarrow{BI}B}\triangleq I\overrightarrow{BI}B\mathrm{,}\overrightarrow{I\overrightarrow{BI}B}\triangleq I\overrightarrow{BI}\overrightarrow{BI}\mathrm{...}\overrightarrow{BI}BI\overrightarrow{BI}\overrightarrow{BI}BI\overrightarrow{BI}\overrightarrow{BI}B\mathrm{...}I\overrightarrow{BI}\overrightarrow{BI}B=\overrightarrow{IB}$$

$$BBI\triangleq BI$$

$$\overrightarrow{BI}\triangleq BI$$

$$\overrightarrow{BI}\triangleq BIBI\mathrm{...}BIBI$$

$$\overrightarrow{BI}I\triangleq BII\mathrm{,}\overrightarrow{BI}I\triangleq BIBI\mathrm{...}BII=BIBI\mathrm{...}BIBI=\overrightarrow{BI}$$

$$\overrightarrow{BI}B\triangleq BIBI\mathrm{...}BIBIB=\overrightarrow{BIB}$$

$$\overrightarrow{BIB}\triangleq BIBBIB\mathrm{...}BIBBIB=BIBI\mathrm{...}BIB$$

$$\overrightarrow{BIB}I\triangleq \overrightarrow{BI}$$

$$\overrightarrow{BIB}B\triangleq \overrightarrow{BIB}$$

$$\overrightarrow{B\overrightarrow{IB}I}\triangleq B\overrightarrow{IB}IB\overrightarrow{IB}I\mathrm{,}\overrightarrow{B\overrightarrow{IB}I}\triangleq B\overrightarrow{IB}\overrightarrow{IB}\mathrm{...}\overrightarrow{IB}IB\overrightarrow{IB}IB\overrightarrow{IB}I\mathrm{...}B\overrightarrow{IB}IB\overrightarrow{IB}I=\overrightarrow{BI}$$

Acknowledgments

This work was supported by the grant of Ministery of Education of the Czech Republic MSM 6046137307.