Predictable Turing Machines
I've been thinking about Turing Machines. And that's due to Nick Drozd's wonderful blog, which showed me Turing Machine research is not only possible, but ongoing.
That shouldn't be surprising, as Turing Machines are notoriously unpredictable beasts.
I actually want to answer one of their posts.
Scott Aronson, in his survey The Busy Beaver Frontier, introduces the notion of a “beeping busy beaver”, which is a Turing Machine that does not halt, but does enter a state of degenerate behaviour. Such notions of degenerate behaviour (a kind of dynamical halting) are interesting because they allows for smaller Busy Beaver programs, as one instruction is not wasted only for halting at the last step. And, well, smaller programs are better.
The problem with quasihalting is that it is undecidable. Not only the problem of deciding wether a machine _will_ quasihalt, but even the problem of deciding if a machine _is_ quasihalted. So he brings back from decades past the notion of Lin Recurrence, which is another notion for dynamical halting – a decidable one. It has a convoluted definition, which hasn't been elegantly put, though it is quite straightforward once you wrap your head around it. Indeed, putting it elegantly something that is left hanging from Drozd's posts.
So I started to think about it. Good concepts should be able to be elegantly put – not only that, but put in a way that makes its meaning _clearer_. And, being how I am, I can't let things that wish to be generalized without generalizing.
---
There's a similarity between the two notions of dynamic halting that we've seen. Both ask from the machine that which halting takes to the extreme: that its long-term behaviour be understandable, _predictable_ in some way. That's the insight.
But there's a difference: in quasihalting, the machine's state [1] is only _partially_ predictable – we know it will be in one of a few labels at a any far-future step, but not which one. In Lin recurrence, we can compute the machine's state _exactly_ – and, crucially, we can compute it faster than just running the machine.
We can abstract this. We can say that a machine is _predictable_ if there is a program (the *predictor*) that runs in less time and gives us the label at a particular step, and the value of any tape cell at that step. Some things to note:
- We couldn't ask the predictor for the _whole_ tape, because that would artificialy require a runtime as large as the original machine, (for, as time progresses, the machine may write to as many cells as steps, and the predictor would have to output that in just as many steps).
- Presumably, we should be asking about only the eventual behaviour, but, by definition, the eventual behaviour must come after a finite time; so we can compute the pre-dynamical-halting behaviour in finite time by just running the machine, and the post-dynamical-halting behaviour by using its predictability.
Let's put it more formally, and then we'll look at how the previous two notions interact with this generalized one.
I'm not saying this definition is definitive; not even that it is good. It's an attempt.
Further, there might be many kinds of predictability, using different properties of machines, so we could be more specific.
Note that, constructively, a machine being predicatble means having a predictor for it. So, effectively, a certificate system will come (as part of the proof that it is a certificate system) with a function from the machine-certificate pairs to predictors for the machine.
That is the case for Lin Recurrence. Indeed, we define `C` to be the type of pairs of natural numbers (the step at which the recurrence starts and the period), and the predicate be that which Drozd describes in their post.
This explains why, intuitively, Lin Recurrence describes some form of dynamic halting. Halting is the ultimate way a machine can become predictable, but not the only one. But my definition, I believe, gives a very general way to think about predictability of Turing Machines.
---
There's still the issue of quasihalting. It doesn't seem to be a form of certificate system. Afterall, even knowing a machine is quasihalted does not allow you to compute its complete state faster than just running it. So we need an alternative definition to accommodate it.
We may refer to this notion, for ease of communication, as _quasipredictability_.
This is _very_ general. Indeed, halting machines are `halted`-predictable, where `halted` is the predicate for… halted machines. _Every_ machine is `true`-predictable, where `true` is the predicate valid over every machine. So every machine is quasipredictable. But the important bit is that quasihalting is also a notion of quasipredictability – that which comes with the predicate of being quasihalted (_i.e._, not being in one of a few states).
One caveat: our previous notion is also an instance of quasipredictability. Maybe. The predicate would be that of “having at step `k` the state computed by the predictor” – so it _is_ an instance only if `k` is considered to be part of what we call “state”; if you don't like this, you might ask for a natural number-indexed family of predicates (`P_k`-predictability). Anyway, this is what I said before: quasipredictability is a sort of predictability where perhaps not the _entire_ state can be known at a particular step. Identity is the most certain predicate, in a sense, so any other predicate is a kind of partial certainty, partial information.
---
Have I solved Drozd's problem of defining Lin Recurrence in a more elegant way? No, not at all. We would still have to state the definition of the Lin Recurrence predicate in his words to give it as a sort of certificate system. But I do believe I have found a better notion: that of predictability itself. Lin Recurrence, afterall, is only a (somewhat elaborate) certificate system. But it is not, I posit, the only one. There are predictable machines that may not be Lin-Recurrent, and they might be interesting.
One nice feature of Lin Recurrence is that is is semidecidable; so there is some program that generates Lin certificates for machines that are Lin certifiable. But is is not entirely decidable!
So, we are not losing anything by talking about predictability. Indeed, we gain something: the possibility of discussing semidecidable and decidable certificate systems. As I said, Lin Recurrence is of the former kind, but we might look for decidable ones, even entirely undecidable ones. Note, further, that quasihalting is _not_ an undecidable certificate system.
In further work, I wish to look at what structure there might exist in the type of all certificate systems, and perhaps all notions of quasipredictability. Then, take some good examples and look for Beasy Beavers for the respective problems! Perhaps I'll look for a better definition for Lin Recurrence (in terms of causality, maybe).
Notes
[1]: By “state” I mean the conjunction of tape configuration, head position and what has been traditionaly called “state”. To the latter I shall refer as “label”, as per Drozd's suggestion.