A recent post discussed the problem of a periods functions which, when given a potentially infinite list, will reliably determine whether that infinite list is periodic and, if so, with which parameters. It was claimed that a general strong periods function, which always works, is impossible because it would imply a solution to the unsolvable halting problem. Instead, a weaker, but still useful, periods function was offered that produces useful output, but does not terminate on infinite lists.
In particular, it was claimed that:
Even if, somehow, the periods function was able to peer into generator of the elements, the problem would remain untractable. Surely, a sufficiently clever, introspective periods function could identify with certainty the periodicity of many infinite series. But in the general case, this introspection would be the equivalent of solving the halting problem which, by famous proof, is impossible.
Here, it will be shown how such a cleverer periods function could often be made to work, but would still ultimately have to fail. But first a necessary digression in how non-strict functional languages, like Haskell, work underneath the hood and how this makes nifty features like infinite lists possible.
In a strict language, as almost all are, when a function f x is called, the computer first evaluates x and then calls f with the value of x. Not so in a non-strict language. Instead, f is called immediately and, rather than the value of x, it is instead given the unevaluated x. Then, when f is running and it needs the actual value of x—which may never happen—the code to evaluate x is run.
In practice that works by giving f a thunk for x. A thunk consists of two parts: A pointer to a function and a list of parameters which the x needs to operate on. This is enough for f to evaluate x when needed. But this fact is largely hidden from the programmer. Unless the programmer is introspective enough to wonder why some code runs terribly fast and other seemingly equivalent very slow or how seemingly impossible structures like infinite lists are easily handled, the programmer will never know.
Now imagine if Haskell had a both very useful and very dangerous operator for pointer-equality. Let's call it (===). This operator, rather than testing whether two values are the same (which for infinite structures would take an infinite amount of time), would test whether two variables point to the same object. In particular, when comparing two thunks, it would just check whether they point to the same function and have the same associated parameters. Such an operator would be straight-forward to add to Haskell and it would always terminate very quickly. It could return False, even for variables that would test as True under (==) because two different bits of code generated the same value. But, importantly, a===b would guarantee that a==b too.
Using the === we could write an augmented periods function that would accurately report on periodicity of a great many infinite periodic lists. In addition to what our weak periods, such an augmented periods would just perform a === check on every tail of the input list and, if it yields True, terminate immediately with an assurance that the list is infinite and periodic.
Consider the function on which we tested our weak periods function:
decimalsRecip :: Int -> [Int]
decimalsRecip n = go 10
where
go 0 = []
go a = let (d,m)=divMod a n in d:(go (10*m))
As the periods function went through the list generated by decimalsRecip, it would very soon get only thunks pointing to the same go function. The parameters carried by each thunk would consist of the express parameter of go, \(a\), and also \(n\) which captured by the go closure and is necessary for it to operate. But \(n\), as well as the pointer to the go code, stays the same in every thunk. Moreover \(a\), the only part of the thunk that varies, is bounded (by \(10 n\) above and \(10\) below) and integral. So—by the same reasoning that one once proved that the decimal expansion of the reciprocal of any integer must be periodic—\(a\) too and hence the entire thunk has to repeat. Hence augmented periods function would terminate and accurately report on the periodicity of decimalsRecip.
So have we solved the halting problem and proven that fool Turing wrong? Not quite. Consider this modified version of decimalsRecip:
decimalsRecip' :: Int -> [Int]
decimalsRecip' n = go 0 10
where
go _ 0 = []
go p a = let (d,m)=divMod a n in d:(go (p+1) (10*m))
The only difference is that decimalRecip'—for some ineluctable reason—keeps a count of the position of the digit it is currently producing. But the output of decimalRecip' is the same as the output of decimalRecip.
If we set our augmented periods function on decimalRecip' it would fail to detect the infinite period because, while the results would still be periodic, the thunks would carry along the position, which never repeats.
But that is an obstacle that can be overcome, you might claim. Surely the compiler would optimize away the completely useless \(p\) variable. Possibly. But you will still always have lists for which the thunk parameters are in some complex, interwoven manner non-periodic, but the results are periodic.
Consider the Riemann Zeta function, a complex function which goes to zero many times in the positive-imaginary part of the complex plane. It would be a straight-forward task to write a function RiemannZeros, which produced a list of the real parts of any such zero, in order of ascending imaginary part. If you ran RiemannZeros, you'd find that it produces a seemingly infinite repeating list of \([\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}, ...]\).
If you set your even cleverer periods function on RiemannZeros it would have tell you whether the result really is an infinite list of \(\frac{1}{2}\) or not. But the answer to that question is the Riemann Hypothesis, the greatest outstanding problem in mathematics and with enormous theoretical and practical consequences! In other words, just to work on RiemannZero, the periods function would have to automatically solve a problem which has resisted the concentrated efforts of a large number of the most gifted exemplars of our species for over 150 years. And even if somehow one could write a periods function that smart, it would still be necessity have to fail on some other list.
