Let's say we have 1D cellular automata, bounded at beginning.

The following is solution for halting problem - mathematically unproven, somewhat open here and there, but basically very near to what I have seeked.

As I have lately rephrased the problem itself and how to solve it, it's here:
1. We can not, possibly, find a general solver, but we should look for what is possible. FSM solver has a weakness in that it can not solve theoretical algorithms - solving infinitely growing number, just an iteration, would take a very long time. This is a theoretical infinity we should be able to handle.
2. The most general solver possible will do the following: analyze the whole picture logically, finding all strong implication rules; figure out all possible logic moves, which lead to hanging. Detecting not hanging is not priority as this can be detected by running program. As there is no upper complexity limit of a program, solver must guarantee only one thing - that it grows in it's logic in such ways that it will make a move in any given direction after any given time moment. This means - it must guarantee that it reaches whatever logic possible at some point in future.
3. I rather try to not play with mathematics (arithmetics etc), because math is not complete itself. If there is anything complete, this is mathematical logic. I think it should be able to handle the cases of combinatorics, which are solvable at all?

I am here trying to do this - to go through all possible abstractions of a program, which one can create, until eventually some of them gives a hang sign - an implication showing that something will grow into infinity. If 1D CA does not grow into infinity, we can check it with FSM method - if it does, we need more powerful one. Now - I don't know if there are questions solvable by computer (particularly in general case) and still not expressible with mathematical logic. We know that Russell failed in making logic into foundation of math, but there is a question - can combinatorics with infinity be based on logic? And can it be based on logic, which does not directly use numbers? I know that FSM is purely based on such logic I meant - but future states of indefinitely growing CA? Will we reach, at some point of time, a conclusion that a thing hangs if it does? This, here, is one more try to put together one aspect of my research over time, including things I have lately found. I suppose that programs, which do not halt, usually have some pattern producing that non-halting. I do not go into nonhalting problems themselves, but the following would be able to solve all mistakes I can remember from myself.


It goes a whole lot further in creating a general halting problem solver, but I am not sure, how far.

We want to detect if it is infinitely growing or not.

We need the most general-case solver we can achieve with mathematical logic.

First we create set of all possible states of one cell. We create a map of all possible sets of those states (except an empty set).

This is the first layer of state map.

We now create implication map - which states imply which states, considering all possible states on both sides of our map.

Now we make our map bigger by one cell - we are going to cover two-cell area. This area's possible states go to our state map as regular members - we can consider them as members and we will calculate all possible states etc. Remember that we have the state groups in addition to states - all possible groups we can form. Of course, one-cell group can not transform into two-cell group, but it can have such as a neighbor.

Now, we gave the total sum of all ways states can change. What implies what. This covers all relations between all state groups - we know, which groups imply which ones.

We will start growing our cell group bigger and always calculate all implications. In many cases, cells and several-cell-groups can form groups with each others.

We start growing in time. We have also time flag "infinite" - for example, the group of all possible states will stay everywhere infinitely (every cell must be at some state of those). Other state groups usually change, but for example, each oscillator (infinitely repeating pattern) must have some group in all possible groups, that all it's states and only those are contained in that group.

We name all states, which combine current time moment with next one, squaring the number of states. Now we can create implication rules with neighbors, which will be in effect in overnext moment. Into this moment, we can imply one-cycle, two-cycle or longer states.

We have now the implication rules of a number of state groups. We lack one thing - generalization ability. We need that for a clear reason - there are exploding cycles possible, which rather change in form, not essence. For example, there might be indefinitely long cell group always carrying our signal.

We now need the knowledge, which implication rules are directly or indirectly implied from which groups of other rules. This means ordered sets of all implication rules. We will pattern-match all new rules - all rules, for shorter or longer slices, for shorter or longer timespans, will be matched to all other known rules. What we are interested in, are direct matches of those (between state groups).

For example, if there are groups A, B, C, X and X, Y, Z, B such that:
A=>B, B=>C, C=>A, X=>A
and
X=>Y, Y=>Z, Z=>X, B=>X

Then we will see a direct match. First ordered ruleset is identical to second one. They are talking about different rule groups, but they give our abstraction ability a kind of completeness - when we know that a set of connections with some specific pattern matches a set of connections with other pattern, we will know that they are of a same kind. One group of states becomes a metagroup to other - some letters are not connected, but A and X are connected and this must be noticed and stored. By a whole set of implication rules and such knowledge we are able to imply that in certain situations, some different groups behave the same.

What this gives us? It gives us such ability:

Imagine number counting: 0, 1, 10, 11, 100, 101, 111, 1000, 1001, 1010, ...

We would not catch the point otherwise than only matching a few things together - namely that the middle parts of numbers are actually the same pattern. They produce similar results - and if we occasionally find rules, which produced the counting itself, and match it to our counter, we will have a meta stategroup. This is really necessary to connect those meta stategroups together with normal stategroups, but I have here some undone homework - anyway, I am sure that this is a question of logic. As we can create new stategroups from beginning part of number, middle part and end part, we need to create stategroups in such ways that if we know that all important implications stay untouched, we can create the group rule, which actually state that in case the end part stays growing (and it's growing must be in some of our longer-time stategroup), the middle part will always propagate the growth to beginning part at some point in future. As we have times of varying lengths, we must also be able to generalize those - we will need to find rules, which are not time-centric, but simply follow each others. To join those rules with surroundings, we need to catch a lot of points here how to handle those things in 2D - this is actually why my first text is specifically about 1D world. If things grow, the same pattern of events will possibly happen in bigger an bigger time frames. Indefinitely. And this indefinite growth of same pattern is the reason, why we have those means for metagroups - otherwise we would never detect any growing pattern.

It is - my intuition states that we have a middle part of a number, say 1101, and a middle part of another number, say 101, then the rules by which first is composed by second, stating that the composer of a number will go as much farer as needed, will also produce the knowledge that the same would apply to potential 11100. That would happen, because this growth certainly has some logic and if it does, then it should be included in sum logic. In the same way - for prime calculator, we can not say, which primes it will calculate (and if it will give null division error?), but we can find some common logic, which is there to produce more and more primes. And this, actually - how to logically solve each single problem and detect if it is solvable in such way, too - is not in scope of this text nor me right now. This is more like an architecture document for general solution than one itself.

This implication set matching, now, in addition to those generalizations, solves our second problem - it allows us to find all possible rules in things, which grow explosively. And to show the logic, this is simple:

1. We need to know all implication rules about which effects our systems produce on the empty world at right side.
2. In case we have clear implication rules, which say that there will appear on right side of us something, which will produce something on right side of itself, which will produce... Then we need to match together the rule and the metarule in such way that by implication rules we could see that things in the rule, which produced right-side activity, match metarules controlling that right-side activity. From that we could tell that the right-side activity will indefinitely produce new levels of right-side activity, which doesn't directly match neither pattern.

Now, we need a whole-universe observer. This observer looks at all the implication rules of world cells and infinity - for example, if my neighbors never produce event X, I will never produce event Y; also patterns of neighbors about that if my neighbors never produce event Y, I will never produce event X. Matching this together you will know that one side there will never produce X and another will never produce Y. By just watching cells it's impossible to say. By knowing that, you can delete a big bunch of state groups and things get simpler - not only simpler, but you are nearer to solution. By deleting all impossible state groups of all cells (and infinity), you might delete those state groups, which keep you doubting if things hang. Each round, you will statically analyze the whole situation and remove more doubt. Only this observer allows to keep all facts together. This means - each frame things should be looked as one logic, all implication rules executed and impossibilities removed. This part happens on a real world we run and it will lead us to understanding of our situation. It removes everything we know to be false. Eventually it might remove the possibility of halting (related state group from some cell).

Running the world - in same way as actualities are interacting and working, both CA style and world-stopping are used to grow certainty in different aspects of future. CA style interaction between cells will show them the future happenings from all aspects we know as general case. Whole-world analysis is necessary primarily to interact with infinity (as our cell stategroups will eventually grow to handle all locality).