I introduce the term "topological identity of computer programs" and show it in relation to halting problem and similar problems - what we need to detect in code to suspect it? I think that considering topological identicalness, we have one more way to get rid of halting problem - which, basically, boils down to the fact that if a program actually does not do something, we can not say that it has a potential to do that. Anyway, topological identity model would give us a way to say so - program might have a potential, which does not happen, but is measurable in very formal mathematical way.



If you can formally prove if a program is having the whole logic of itself inside it to make a decision, you have recognized the layer of logic necessary to solve the halting problem - nothing more is needed. Such program can not fool itself. I even think that this "hanging condition" can be added to my 1D solver.

How it formally looks like?

1. You will remove noise around some block of code - at each moment, you will have all inner logics and proofs that outer logic will not interverne.
2. You will prove that the result of this inner logic is going to determine, how outer logic behaves.
3. You will prove that those are "topologically" identical.
4. You return third error code not meant to say anything about actual behaviour.

How this solves the halting problem (as we know that outer logic in each case of a halting problem actually will intervene by stopping a detection)?

We can actually always prove that the inside and outside are not topologically similar, but they are topologically identical.

Full analysis will always reach the point, which can be expressed in fortran (we will have something exactly like that):

Topology, here, is an identical base layer of conditions.

1. That there is, in code, for each DoesHalt, some next DoesHalt.
Topology(DoesHalt(x+1)) = Topology(DoesHalt(x))
2. That the result of those DoesHalts is in a very clear connection to outer program.
2a: If BecomesTo(DoesHalt(x+1), A(x+1)) then BecomesTo(DoesHalt(x), A(x))
2b: If BecomesTo(DoesHalt(x+1), B(x+1)) then BecomesTo(DoesHalt(x), B(x))

A and B here are the condition groups of exit and hang. We actually need to catch the time-dependence - for each DoesHalt in cycle, lower level of DoesHalt will take some more time. Thus, to detect the condition is impossible - as they are topologically identical and each needs to give the lower level at least a time needed to detect this identicalness, they can not halt.

Now, we need to make a deduction that A(X) means hanging in our context (big X is any possible value of x). By doing so, we have actually deducted that even in case our cycle halts, the whole thing will hang. Now we do not care about 2a anymore. Finish condition of 2a means hanging.

So, 2b is halting condition. It says that a program will hang, so it would halt right after that. We have, surely, purified the whole function out so that we will see the dependency cycle - we see that this part of function depends on what the whole function will do. This is the only feedback point of the whole function - if this point is reached, the function will exit and the program will continue running. We will also see the topological identicalness between the whole function and that point.

We will have the following circle in our memory:

A: function X(i)
B: if X(i+1) == True then X(i) = False
C: if X(i+1) == False then X(i) = True
D: end function
E: X(i+1) = X(i)

Whatever the functions do, we can have that circle. That could even be reached by static analysis.

Now, what we are going to decide? We could, for instance, calculate the inside of that function and with our method find out that it will equal False (in case we equal True, which we plan to do). That circular dependency _will_ exist there - nothing can remove it, however we change the conditions! That we know by Turing's proof. But we also know that we can detect the circular dependency.

Now, we see there a code specifically designed to find that circular dependency and halt in case it exists. Now, the question is - can we detect that code in general case? As this code makes the function to halt and the normal code flow to continue (and it does, because the function must, in fact, return False - any kind of error signal).

We will deduct that code out by fact that it depends on return value of itself in _unchanged_ form and that the program flow is dependent on it's return value - which, in this case, is True. Such program, even if it halts, is buggy.

For example, we can take another case:
function A() {
  if A() return not A();
}

This is an infinite cycle. In all cases, function must not call any function, which is it's topological equivalent - whatever the return value.

By topological equivalence I mean very specific thing:

If you create two infinite state machines and their states, when ordered as A, B, C, D, ..., are orderable in such way that each change rule has identical change rule in another, then they are topologically equivalent. In case one of them has possible groups of states (A, B), C, then:

if A=>C and C=>B, but other parts of program can only change A=>B and B=>A, but not A=>C, B=>C, C=>A, C=>B, then

And there is another machine with rules D=>E and E=>D.

And those changes can take any time, but are guaranteed to happen in this FSM.

Groups (A, B), C [two groups] of first machine are topologically equivalent with
Groups D, E of second machine

And thus the first machine with states A, B, C contains virtual machine, which is topologically equivalent with second one. For all machines, we can find such topological equivalents. In case of non-FSM, topological equivalence becomes more complex, but as it never reaches infinite size, all it's possible states can be counted - and if there is a fit, there is topological identity.

In case some virtual machine depends in it's output on some other, topologically identical machine, which it creates - and which is, thus, created also by it's topological equivalent - so that also this equivalent depends on the same things, it is, in fact, running into some kind of halting problem or similar. We must only be able to show that the identical machine inside is independent - it might depend on some activity of parent machine, which is also it's own activity, but it must not be dependent on anything other. For example, it can not get input variable, which it gives to next one after dividing one.

When we analyze topological space of possible computer programs, we can divide most programs into several pieces in however way so that both pieces will be state machines interacting with each others. This is why my 1D CA solver essentially does. By analyzing such topology we will get a lot of information about programs otherwise unachievable.

Now, our solver can show us in IDE, which calls are circular.