The Undecidable Club

undecidable_club.md

There is a club called Undecidable, but they don't let in just any old question. In order to be admitted to the Undecidable Club, a question has to prove that she's seriously hard. How hard? Well, let's talk about the membership process.

First, the applicant needs a sponsor (Let's call the sponsor S). Your sponsor is some question who's already in the club (so you know they're hard). In order to get into the club, an applicant has to show she's just as hard as her sponsor (Let's call the applicant A). How does A prove her difficulty? She has to show that if some Turing Machine could solve A's problem, it could solve S's problem as well. Since we know S is hard (he's in the club already!), A's problem must be just as hard.

Membership Roster

These problems are all known to be hard. You can choose whichever you like to be your sponsor.

• function AcceptsOwnEncoding(T)
• function AcceptsSomething(T)
• function HaltsOn(T,w)

Example Applicant: HaltsOnLambda

Let's consider a question who wants to join the club, function HaltsOnLambda(T). It chooses as its sponsor HaltsOn, as they seem to have a lot in common. If we want to help HaltsOnLambda(T) join the Undecidable club, we should phrase HaltsOn(T,w) in terms of HaltsOnLambda(T). That shows that HaltsOnLambda is just as hard as HaltsOn.

// An alternate definition of HaltsOn,
// Showing that it's no harder than deciding
// the answer to HaltsOnLambda (so it should
// sponsor HaltOnLambda into the club).

function HaltsOn(T,w){
    // We need to create a payload Tobj,
    // for which the truth of HaltsOnLambda(Tobj)
    // is the same as the truth of HaltsOn(T,w). 
    // (both false or both true).
    var Tobj = function(ignored_parameter){
        // simulate T on w.
        return T(w);
    };

    // Since Tobj("") performs T(w),
    // If Tobj halts on "", then
    // T halts on w.
    return HaltsOnLambda(Tobj);
}

Since we can write HaltsOn(T,w) in terms of HaltsOnLambda(T), we know that HaltsOnLambda is just as hard as HaltsOn(T,w). You might also think of it as being just as general. We can use HaltsOnLambda to answer the same questions as HaltsOn(T,w).

Example Applicant: ReturnsToStartState

Now that HaltsOnLambda is enjoying the benefits of membership in the Undecidable club, it is allowed to act as a sponsor for other problems. A newcomer, ReturnsToStartState(T) decides to choose HaltsOnLambda as a sponsor. So we need to phrase HaltsOnLambda in terms of ReturnsToStartState(T)

//An alternate definition for HaltsOnLambda,
// Showing that it's no harder than deciding
// the answer to ReturnsToStartState

function HaltsOnLambda(T){
    var Tobj = function(T){
        startState(); // do nothing state
        T(''); //Simulate T on Lambda
        // Return to the start state (as long as T('') is finished)
        startState();
    };

    // Tobj will only return to startState()
    // if T terminates on ''.
    // So this truly answers the question "Does T halt on Lambda?"
    return ReturnsToStartState(Tobj);
}

The Big Idea

If we were writing one of these proofs out formally, it would start like this

Suppose <my-problem-that-I-actually-think-is-not-decidable> is decidable. Then there is a Turing Machine D that decides it.

Then we describe a way to take some known-to-be-hard problem, like the Halting Problem, and show that we can use D (along with some trickery) to decide the known-to-be-hard problem. But we know the Halting Problem is undecidable.

So this Turing Machine D cannot exist, and our supposition was wrong. In fact, <problem-that-we-actually-think-is-not-decidable> is undecidable.