Where Hard Meets Easy
Some hard to compute functions are easy modulo a number
Georgia Tech source
Joseph Ford was a physicist at Georgia Tech. He earned his undergrad degree here in 1952, and after earning his PhD at Johns Hopkins, went to work for two years at Union Carbide in Niagara Falls before joining the University of Miami and then coming back to Tech. He was possibly lured back into academia by considering a paradox studied by Enrico Fermi, John Pasta, Stanislaw Ulam, and Mary Tsingou in the mid-1950s. The paradox is that periodic rather than ergodic motion can often result in complicated systems.
Today we wish to present a simple observation about hard-to-compute functions.
Ford was one of the founders of chaos theory and was instrumental in creating the journal Physica D for nonlinear dynamics. While becoming a Regents’ Professor at Tech in 1978 he was an early adopter of personal computers for his work. This accompanied a progression in his thinking expressed in the entire abstract of his 1983 paper, “How Random is a Coin Toss?”
In examining the differences between orderly and chaotic behavior in the solutions of nonlinear dynamical problems, we are led to explore algorithmic complexity theory, the computability of numbers and the measurability of the continuum.
This paper includes a photo of the coin toss before a National Football League game—something to think about for Sunday’s Super Bowl. For now, though, let’s think about how periodic phenomena might creep into uncomputable functions.
Natural Hard Functions
If is uncomputable, can it be possible that is computable modulo for some ? This is especially interesting when might only be uncomputable “because” it grows faster than every computable function.
The answer is quite simple: Yes. Suppose that is hard and consider . Then is always zero modulo , but knowing yields . This trivial answer—yes it can be easy to compute a hard function modulo a —calls to mind an old theory saying:
Too easy an answer to a problem suggests there is a better problem.
Let’s look for a better problem.
The difficulty with the function is that is artificial: we took a nice hard to compute function and changed it so it would be easy to compute modulo . This seems like “cheating”—no? So the better problem is to ask: are there natural hard problems so that they can be computed modulo some ?
A classic hard function is the halting problem, but it is only – valued and so will not be very interesting. The reason, of course, is that computing it modulo any yields the same value. So let’s look at a cousin to the halting problem: the busy beaver function, which we recently discussed.
Define to be the maximum number of 1’s that an -state Turing machine can leave in a halting computation that starts with a blank tape and uses only the characters 1 and blank. The Turing machine has just one head and must move it one cell left or right at each step; the tape is two-way infinite. A variant allows the machine also to stay—that is, not move its head—and this gives rise to a function .
Beaver Census and Turing Symmetries
I do not know whether we can compute or modulo any . It seems unlikely, but is not obvious to me. However, we can define a natural quasi-inverse of the busy-beaver function that is likewise uncomputable, but is computable modulo 2:
Definition 1 Define the beaver census function to be the number of n-state Turing machines that when run on blank tape halt with at least k-many 1’s on the tape. is defined similarly for Turing machines with “stay” moves.
If were computable, then we could compute by iterating until . Likewise is uncomputable, and this is interesting because both functions are bounded by the number of -state Turing machines of the respective kinds. These numbers are singly exponential in , so the uncomputability is apart from growth.
There are two “obvious” symmetries of Turing machines that affect the values of . One is that you can permute the state labels. Let us insist that the start state is labeled ; then there are the permutations of the other states. The second is handedness. Since the tape is two-way infinite, we can interchange “left” and “right” moves in every instruction to produce an equivalent machine that runs in mirror image.
Does this make and/or always be multiples of –? One immediate subtlety is that in the latter case when a machine has only “stay” moves, interchanging “left” and “right” does not produce a different code. Such a machine can leave at most one 1 on the tape, so this is immaterial when . For other machines the interchange cannot produce the same code as otherwise the machine would be nondeterministic, having both a “left” and “right” option at some state.
However, what can happen is that the left-right interchange has the same effect as a permutation of the states. Say that such a machine has an “unexpected symmetry.” This is what makes our problem nontrivial:
For which divisors of are and/or computable modulo ?
Modulo 2 and Modulo
The only thing we can prove now is that the interchange symmetry is always available.
Theorem 2 and are computable modulo in polynomial time. So are their analogues for the busy-beaver measure that counts the number of steps before halting rather than the number of 1’s left on the tape.
Proof: For the left-right-only case the values are always even. For with , we can exhaustively simulate every machine having only “stay” moves since there is no unbounded interaction with the tape. There are still exponentially many machines to count, so polynomial time is not completely trivial. Every machine with state set is characterized by a graph on nodes. Each node is labeled either or for some state and expresses that the machine is looking at a blank or at a 1, respectively. Letting stand for the start state ( by our convention in the last section), becomes the root node in the graph. An edge represents that the machine has an instruction for state that changes blank to 1 and goes to state . An edge means that the machine in reading 1 leaves it alone and goes to ; the other four kinds of edge are defined similarly.
Thus we have to count the number of graphs of out-degree at most 1 on nodes in which the path beginning at never cycles and ends at a node in . To do so, for each possible length of such a path, we multiply two numbers: the count of such paths, and the number of ways to define irrelevant links (and non-links) from the other nodes. Summing those values over gives . The treatment for the step-counting measure is similar, except that the path need not end in .
Does this idea extend for the other divisors of —? Of course if the functions are computable modulo then they are computable modulo the others. We might expect that machines with an “unexpected symmetry” cannot be among the busiest beavers, so that we can discount them as soon as , perhaps.
What we are more curious to ask, however, is this:
Are there any other symmetries of Turing machines? Perhaps ones that emerge only when is sufficiently large?
Note that for , is the number of Turing machines achieving the busy-beaver bound. Thus our results about apply to the busiest beavers. Hence a way of looking for more symmetries is to see if has any larger divisors than . That is, are there busiest-beaver machines besides those that are equivalent under the “obvious” symmetries? The studies which we cited before seem not to have found any.
Can we find (other) interesting cases of uncomputable functions being computable mod ?