- That you can not check if program does not halt. You can always check if it does.
- That the finite state machine solution does not cope with infinities - it has no way to understand anything about that. It wont detect any infinitely growing program as hanging.
- Cellular Automata is more pure and mathematical thing than a computer - it does not have this messy differentiation between memory, processor, instruction set or code pointer. Thus it's far better machine to think about halting checkers - it's the one, where you could think about general formulas without thinking about the complexity of modern processor or programming language.
The main theorem about halting problem solver is the following:
The halting problem will eventually solved by program, which is able to expand it's knowledge in space of non-halting programs or signs of such program in such way that for each point of time there is some future point of time in which it will go deeper in any given dimension of that space.
Dimension of that space - when you do some operation, which makes your knowledge wider, you are usually making it wider in some given dimension. For each dimension, where it always eventually happens, you will also eventually reach any given point.
And to expand it's knowledge in space of signs for non-halting programs - if you constantly learn such signs and you are given a program, which wont halt, then if you have some certainty that eventually you will detect that it wont. For programs, which halt, you will eventually detect that they do - just by running them.
Text itself covers a set of my ideas about how to detect patterns in Cellular Automatas. This is a really interesting area, where I have grown over time.
Lets hypothetically design a Cellular Automata computer. All computers are designable as CAs.
CA consists of "cells", each cell having some simple rules about interacting with other cells.
1. We define an "exit" state of a cell - when any cell reaches this state, our program will halt. All other states are designed for actual work.
2. For all cells, we have a map of all possible states of them.
Why we need this CA? Because the computer-code-memory complex is enormously complex and does not allow for simple rules.
We want the simple rules - simplest we can get. We want to analyse the program, using all possible mathematical logic to predict it's potential outcome. We want to predict if it will never halt. We already have the formulae for a system, which is finite - now we want some formulae, which could cover infinite systems as well as possible. Probably we can not do as well as we would like, but this thing here is nearest I could get.
We have two parts of our thing - the locality and an infinity. We want an ideal solution for finding all repeating patterns, covering very complex sets of interactions and dealing with this infinity at some level. We need an actual state and hidden state for our cells.
An actual state is the current state - 0 or 1 - of a cell. We are needing to cover bigger chunks, thus we start growing that state:
1. We create static all-possible-value maps for 3*3 (then 5*5, 7*7 etc.) areas.
2. We size all the rules we have got up to that all-possible-value map.
3. We group all possible states of our new cells, bigger and acausally connected (having some shared information) into all possible groups and find implication rules between those groups - which ones make which ones certain, which ones make which ones impossible. We do not need to look at neighbour cells as the logic is contained in each cell. We know, which ones of those states are exit states.
Implication rules specify such things - if a neighbour cell is in state of that group, then we will never anymore reach state of that group; if all neighbours fall into that group, then this group there is impossible etc. All rules we can get - mathematical logic allows us to just iterate over all possible rules. As we see definite, impossible etc. states of our neighbours, also, this information will spread over map.
We make it clear if we are sure in something about the future. Things we can be sure in:
1. We will reach some state groups after 1, 2, 3, 4, ... ticks.
2. We will stay in some state group forever after x ticks or we will never reach them after x ticks.
With those rule groups, we can do the following:
1. Find closed loops and the state groups, which are impossible to achieve in our current state of affairs (we can not reach them, because when we look the implication rules about the whole world and infinity around it, we can see that they are unreachable). So we will delete all states alltogether, which we will never reach.
Now, we will start propagating the information about future - as more exact, as better. For that purpose, we are going to grow in time as fast as we are growing in space; each cell will become more conscious about it's future. It's important to notice that we are keeping all dimensions grow in same speed - it's necessity to always be sure that in future, each dimension will grow more. Otherwise we would not be able to map the whole space.
We will include future states into our state-map. Once again, we will need this to achieve a very specific constraint - if we know some rules about some future states for sure, we can propagate them into infinity. For example, if we know that some state group is stable and propagating, totally eliminating the possibility of some other state group to propagate, we will mark that infinity around us belongs to that state group. We can easily handle an infinity and only definitive knowledge about future will allow us to really propagate things there - but that is what we need. Cells grow into future and their movement rules grow accordingly; we can also make time go faster and start jumping over many ticks each turn.
We should also notice that for now, infinity is a cell in it's own right. Anyway, it must take all neighbour cells into consideration, not just one. It must live it's own life, change in time - take forms a cell would take if all neighbours were of same kind. This is a life of potential. Should it become certain about future halt, the task would be solved.
So, our thing is now able to deductively learn about it's own behaviour, but it's not yet able to even count. It is actually better than just checking for repetitions, but not too much. It's cells have a degree of freedom (by the way, you can remove some intermediate cells if they take too much memory or grow some cells together) and it's able to know things in advance - not tick-by-tick, but very general things. It could notice complex patterns. But with growth like such, it is able to count only small integers - not integers of unlimited size. More importantly - it can not find out potentials of integers of unlimited size. It can do a lot of guesswork about the future - it can actually deductively remove a lot of possibilities and find a lot of patterns.
It must now find out some more complex rules. It must grow out from its square borders, but keep the ability of growing into each dimension with constant rate.
We should clearly understand, which fields interact with which ones. As we have got enough data, we could turn our cellular automata into living graph of complex relations. Anyway, this is an operation too complex for now.
So, we have such picture:
1. Ultracomplex infinity, which knows a lot about program's future states.
2. Mathematical model of complex potentials and interactions.
Let's now do two things:
1. Start growing the resolution of infinity.
2. Start "striking" the knowledge into infinity.
Growing the resolution of infinity is quite simple - we make it a cell grid instead of a cell. I suggest multiplying it's width and height with primes in the following order: 2, 2, 3, 2, 3, 5, 2, 3, 5, 7, 2, 3, 5, 7, 11... This has some meaning - you can always copy it's previous content several times into itself. You can do long pauses between growing it if it's good for memory.
"Striking" the knowledge into infinity means searching patterns from it's rules (I hope you still have a connection between rules and cell positions - indexed arrays about relative positions of cells, which are related to some specific elements of rulesets). This, now, gives a way to raise the resolution and thus exactness of your knowledge; it will get more clear patterns and the potentials can distribute very fast.
You can also create a web of horizontal, vertical and diagonal infinite lines and grow that one, too - this will give better resolution to infinity. As all information contained in cells is deductive, it can freely co-exist with infinity. This raises the probability that something will be marked as propagating into infinity for sure - in case you make it sure that if program halts, it will not grow anymore, certainly growing some pattern (and not lack of some) into infinity is a sure sign of hanging. This web should be composed from a series of parallel lines, each repeated infinitely in it's direction.
If you have those cross-infinities, you can also have separate infinity patterns starting from each corner to this cross. This, again, raises the probability of having some sure match.
Comments