Skip to content

Where Hard Meets Easy

January 31, 2015


Some hard to compute functions are easy modulo a number

JosephFordgatech
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 {f(n)} is uncomputable, can it be possible that {f(n)} is computable modulo {q} for some {q>0}? This is especially interesting when {f(n)} might only be uncomputable “because” it grows faster than every computable function.

The answer is quite simple: Yes. Suppose that {f(n)} is hard and consider {g(n) = qf(n)}. Then {g(n)} is always zero modulo {q}, but knowing {g(n)} yields {f(n)}. This trivial answer—yes it can be easy to compute a hard function modulo a {q}—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 {g(n)=qf(n)} is that is artificial: we took a nice hard to compute function and changed it so it would be easy to compute modulo {q}. 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 {q}?

A classic hard function is the halting problem, but it is only {0}{1} valued and so will not be very interesting. The reason, of course, is that computing it modulo any {q>1} yields the same value. So let’s look at a cousin to the halting problem: the busy beaver function, which we recently discussed.

Define {BB(n)} to be the maximum number of 1’s that an {n}-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 {BB'(n)}.

Beaver Census and Turing Symmetries

I do not know whether we can compute {BB(n)} or {BB'(n)} modulo any {q>1}. 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 {BC(n,k)} 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. {BC'(n,k)} is defined similarly for Turing machines with “stay” moves.

If {BC(n,k)} were computable, then we could compute {BB(n)} by iterating {k} until {BC(n,k) = 0}. Likewise {BC'(n,k)} is uncomputable, and this is interesting because both functions are bounded by the number of {n}-state Turing machines of the respective kinds. These numbers are singly exponential in {n}, so the uncomputability is apart from growth.

There are two “obvious” symmetries of Turing machines that affect the values of {BC(n,k)}. One is that you can permute the state labels. Let us insist that the start state is labeled {1}; 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 {BC(n,k)} and/or {BC'(n,k)} always be multiples of {m = 2\cdot(n-1)!}–? 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 {k \geq 2}. 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 {q} of {m} are {BC(n,k)} and/or {BC'(n,k)} computable modulo {q}?

Modulo 2 and Modulo {q}

The only thing we can prove now is that the interchange symmetry is always available.

Theorem 2 {BC(n,k)} and {BC'(n,k)} are computable modulo {2} 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 {BC'(n,k)} with {k = 1}, 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 {Q = \{1,\dots,n\}} is characterized by a graph on {2n} nodes. Each node is labeled either {q_0} or {q_1} for some state {q \in Q} and expresses that the machine is looking at a blank or at a 1, respectively. Letting {s} stand for the start state ({s = 1} by our convention in the last section), {s_0} becomes the root node in the graph. An edge {(q_0,r_1)} represents that the machine has an instruction for state {q} that changes blank to 1 and goes to state {r}. An edge {(q_1,r_1)} means that the machine in {q} reading 1 leaves it alone and goes to {r}; 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 {Q_0 \cup Q_1} in which the path beginning at {s_0} never cycles and ends at a node in {Q_1}. To do so, for each possible length {\ell} 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 {n - \ell - 1} nodes. Summing those values over {\ell} gives {BC'(n,1)}. The treatment for the step-counting measure is similar, except that the path need not end in {Q_1}. \Box

Does this idea extend for the other divisors of {m = 2(n-1)!}—? Of course if the functions are computable modulo {m} 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 {k > BB(n/2)}, 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 {n} is sufficiently large?

Note that for {k = BB(n)}, {BC(n,k)} is the number of Turing machines achieving the busy-beaver bound. Thus our results about {BC(n,k)} apply to the busiest beavers. Hence a way of looking for more symmetries is to see if {BC(n,BB(n))} has any larger divisors than {m}. 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.

Open Problems

Can we find (other) interesting cases of uncomputable functions being computable mod {q}?

7 Comments leave one →
  1. February 1, 2015 10:27 am

    Scott Aaronson and I discussed a related problem see comment #44 here and following discussion http://www.scottaaronson.com/blog/?p=1385 . He gave a version of the problem there to some of his students. You may want to talk to him to see what the state of that currently is.

    • JacksonA permalink
      February 1, 2015 1:26 pm

      Thanks for the Scott Aaronson link to the topic…

  2. February 1, 2015 8:37 pm

    busy beaver problem, one of the deepest problems in all of CS very worthy of much more attn but not researched too much because of its intrinsic hardness & perceived hopelessness…. hope that some day science conquers some of the deep mystery of undecidability but for now its almost worse than a stalemate😦

  3. o0o permalink
    February 5, 2015 4:57 pm

    This was a fun article :o)

    By the work of Matiyasevich and Jones on Hilbert’s 10th problem, we should be able to translate any function we like into an explicit Diophantine equation, which we may be able to evaluate modulo q, but not in general.

  4. February 6, 2015 12:49 am

    just ran across this, did you notice this question BB(n) mod x on math.se by yuan? seems to be the same right?
    re oOo’s last comment, think it might be quite relevant.💡 (conjecture) could the BB(n) mod x problem be equivalent to the decidability of solving general Diophantine equations mod(n)? is anything known about the latter problem?

  5. Frank Vega permalink
    February 9, 2015 11:38 am

    Hello Professor Lipton,

    I would like to share a paper which contains a readable solution of the outstanding problem P versus NP. It is known result if there is a problem in coNP and not in P, then this would be sufficient to show that P is not equal to NP. This is exactly what we have tried to do: show and prove the existence of such problem. I think maybe this can be an insteresting paper for you. In one of your blogs you metioned that wrong papers of P=?NP proofs have become in a good controversy to make new theories (like the case of Ted Swart and Yannakakis).

    For that reason I presented as preprint work in

    https://hal.archives-ouvertes.fr/hal-01114642

    and the pdf file in

    https://hal.archives-ouvertes.fr/hal-01114642/document

    while I’m going to try to make some improvements of this initial version before I will send it to a journal.

    In the mean time, any suggestion to improve or refuse this work will be truthfully thanked.

    Regards…

Trackbacks

  1. undecidability: the ULTIMATE challenge | Turing Machine

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s