How to Call Imaginary Functions

2025-02-01

The concept of Turing Reductions (Unterprogrammtechnik) make up a huge part of the lecture's chapter on computability. In the lectures, it is used to prove that a certain language is undecidable by creating a Turing machine deciding an undecidable problem while using the Turing machine of our target language as a subprocedure. Let's look at a couple examples now to get a feeling.

Waitwaitwait, what do you mean a Turing machine deciding an undecidable problem? How can an undecidable problem can be decided?

It's a classic form of proof by contradiction. To show that a certain proposition is wrong, you first assume that the proposition is correct. Then, you deduce another proposition from your previous proposition which evidently leads to a contradiction.

There are lots of real-life examples of proofs by contradiction. An example would be a criminal suspect providing an alibi. Given the prosecutor's accusation, the suspect is essentially telling the judge: "Let's just assume that I did it. Then, I must've been at the crime scene when the crime actually happened. But I wasn't, which must mean I didn't do it!"

...Aand what did an undecidable language mean again?

1. Undecidable Languages

A language is a set of words. A word is a finite sequence of symbols from a finite set, also known as an alphabet. Using the English alphabet, $\texttt{power}$ would be an element of the English language, whereas words like $\texttt{Macht}$ or $\texttt{asifj}$ would not.

Now, think of a program which takes any word over the English alphabet and returns a truth value whether the input is part of the English language. If the language contains the input, the program returns true; otherwise it returns false. Do you think you can implement it?

Yeah, if we have access to the set of all English words, it should be something like this:

TypeScript
function isWordInEnglishLanguage(word: string): boolean {
    const englishDictionary = new Set<string>([...]); // All possible English words
    return englishDictionary.has(word);
}

Right. Genereally speaking, if there is a program $M$ able to give a yes-or-no answer whether the word is in a certain language $L$ or not for every word over the alphabet, we say the program $M$ decides $L$ or $M$ is a decider of $L$. Furthermore, we say that the language $L$ is decidable. In the computer science context, we typically work with the binary alphabet $\{0, 1\}$.

The algorithm above actually works for all languages as long as the language is finite. We can simply iterate over our dictionary and check for its membership given an input. It can therefore be said that all finite languages are decidable.

There are lot of infinite languages which are decidable as well. An example would be a language of words ending with a symbol 1 over a binary alphabet:

TypeScript
const endsWithOne: boolean = (word: string) => word.endsWith("1");

On the other hand, a classic example of an undecidable language is the Halting Problem:

$H$: Given a program and an input, does the program terminate on the input?

Can't we just call the function with its input and return $\texttt{true}$ whenever the call is terminated?

TypeScript
function haltingProblem(func, input: string): boolean | never {
    func(input);
    return true;
}

This will surely work for all positive instances of the halting problem, but as soon as the function encounters a negative instance, it will be stuck in an endless loop just like the input function. A crucial property of a decider is the ability to not only decide all positive instances, but also to decide all negative instances as well. Programs like above which classify all positive instances of a language $L$ correctly and do not falsely mark any negative instances as positive are called semi-deciders of $L$. $L$ is further called semi-decidable.

So what does the program look like that solves the halting problem?

That's exactly our point; Such program simply does not exist! For an undecidable language $L_1$, it is impossible to generate a program that correctly determines the membership for every input. So, in order to prove a $L_1$'s indecidibility, you need to prove the non-existence of its decider.

This is where the proof of contradiction comes in. Our argument works as the following: "Let's just suppose $L_1$ is decidable. Then a decider for $L_1$ must exist, but I can show you that I can construct a decider for an indecidable language $L_2$ using $L_1$'s decider as a helper function. The existence of $L_2$'s decider must mean $L_2$ is decidable. But it isn't, which must mean $L_1$ is undecidable!

2. The $\varepsilon$-Halting Problem

Let's try our method on another well-known indecidable problem known as the $\bm{\varepsilon}$-halting problem: Given a program, does the program terminate on empty input?

Alright, so suppose our $\varepsilon$-halting problem is decidable. Then there must be a program deciding the $\varepsilon$-halting problem:

TypeScript
/**
 * @input A program.
 * @returns true if the program halts on empty input, otherwise false
*/
declare function isWordInEpsilonHaltingProblem(func): boolean;

And now, we need to build a program deciding an undecidable problem: Let's take the halting problem.

TypeScript
function isWordInHaltingProblem(func, input: string): boolean {
    // Use inWordInEpsilonHaltingProblem somehow?
}

Here, the trick is to create a new function func1. func1 calls func(input) on empty input and goes into an endless loop otherwise. An interesting observation is that func1 here is never being called explicitly; Instead, we only pass it over to the decider of the $\varepsilon$-halting problem as an argument.

TypeScript
function isWordInHaltingProblem(func, input: string): boolean {

    function func1(input1: string) {
        if (!input1) return func(input);
        else while (true);
    }
    return isWordInEpsilonHaltingProblem(func1);
}

Now, we just need to check whether our isWordInHaltingProblem actually decides the halting problem: If fed a positive instance, our program has to return true; if fed a negative instance, our program has to return false. Our program cannot be stuck in an infinite loop on any input. This part is called proving algorithm correctness (Korrektheitsbeweis).

If func and input are a positive instance of the halting problem, this would mean the function call func(input) will terminate eventually. As a result, func1 will terminate on empty input. func1 is therefore a positive instance of the $\varepsilon$-halting problem and isWordInEpsilonHaltingProblem(func1) should return true, meaning isWordInHaltingProblem(func, input) returns true as well!

Analogously, if func and input are a negative instance of the halting problem, the function call func(input) will not terminate. As a result, func1 will not halt on empty input, therefore being a negative instance of the $\varepsilon$-halting problem. Thus, isWordInEpsilonHaltingProblem(func1) as well as isWordInHaltingProblem(func, input) returns false.

We built a program that decides the halting problem, which is indecidable... There's our contradiction! The $\varepsilon$-halting problem is therefore indecidable.

As a side note: The $\varepsilon$-halting problem is semi-decidable. The implementation is identical to the halting problem's semi-decider. Try to imagine what the semi-decider looks like.

3. Further Examples

All examples below leverage the halting problem to prove its undecidibility.

$H_{never}$: Given a program as input, does the program halt on no input at all?

TypeScript
/**
 * @input A program.
 * @returns true if the program halts on no input, otherwise false
*/
declare function haltsOnNoInput(func): boolean;

function isWordInHaltingProblem(func, input: string): boolean {

    function func1(input1: string) {
        return func(input);
    }
    // Flip the return value
    return !haltsOnNoInput(func1);
}

$H_{all}$: Given a program as input, does the program halt on every input?

TypeScript
/**
 * @input A program.
 * @returns true if the program halts on every input, otherwise false
*/
declare function haltsOnEveryInput(func): boolean;

function isWordInHaltingProblem(func, input: string): boolean {

    function func1(input1: string) {
        // Ignore input1
        return func(input);
    }
    return haltsOnEveryInput(func1);
}

$A_{all}$: Given a program as input, does the program return true on every input?

TypeScript
/**
 * @input A program.
 * @returns true if the program returns true on every input, otherwise false
*/
declare function acceptsEveryInput(func): boolean;

function isWordInHaltingProblem(func, input: string): boolean {

    function func1(input1: string) {
        // Ignore input1
        func(input);
        return true;
    }
    return acceptsEveryInput(func1);
}

$H_{42}$: Given a program as input, does the program halt on the input 42?

TypeScript
/**
 * @input A program.
 * @returns true if the program halts on input 11, otherwise false
*/
declare function haltsOn11(func): boolean;

function isWordInHaltingProblem(func, input: string): boolean {

    function func1(input1: string) {
        if (input1 === "42") return func(input);
        else while (true);
    }
    return haltsOn11(func1);
}

$H_{special}$: Given a program func as input, does func(func) return true?

TypeScript
/**
 * @input A program.
 * @returns true if the program returns true when called upon itself, otherwise false
*/
declare function isWordInSpecialHaltingProblem(func): boolean;

function isWordInHaltingProblem(func, input: string): boolean {

    function func1(input1) {
        // Ignore input1
        func(input);
        return true;
    }
    return isWordInSpecialHaltingProblem(func1);
}

$A_{\lvert 7 \rvert}$: Given a program as input, does the program return true for exactly 7 different inputs?

TypeScript
/**
 * @input A program.
 * @returns true if the program returns true for exactly 7 different inputs, otherwise false
*/
declare function acceptsExactly7(func): boolean;

function isWordInHaltingProblem(func, input: string): boolean {

    const acceptingWords = Array(6).fill(input).map((value, index) => value + index);

    function func1(input1) {
        if acceptingWords.includes(input1) return true;
        if (input === input1) {
            func(input);
            return true;
        }
        return false;
    }
    return isWordInSpecialHaltingProblem(func1);
}

4. Gödel Numbers

Although the logical structure stays identical, the real examples, notationwise, work a bit differently. The notation I used cannot acurrately map all cases of the Unterprogrammtechnik, since it is an abstraction of how it's actually done [1]I could acurrately map all cases using the TypeScript notation since it is a Turing-complete language, but I could not do it in the ways I introduced without making it complicated, which destroys my purpose of introducing it in the first place.. In actual Turing reductions, you would work with Turing machines and their corresponding Gödel numbers. I won't explain the encodings in great detail here, but you can try out my Gödel number converter below.

Looking back at the definition of the halting problem, the same problem applied for Turing machines would be something like the following:

$H$: Given a Turing machine $M$ and an input $w$, does $M$ halt on $w$?

A decider of this problem would be a Turing machine... taking a Turing machine as input... which again taking some input. My head hurts.

Nicely put! But remember, our definition of Turing machines can only take inputs over the input alphabet $\Sigma$, which is the binary alphabet $\{0, 1\}$ in our case. This could be a problem, since Turing machines are a mathematical tuple, not a 0-1-string. Gödel numbers are just a way of encoding Turing machines into a binary string format. The halting problem therefore formally looks like this:

$H$: Given an encoding of a Turing machine $\langle M \rangle$ and an input $w$, does $M$ halt on $w$?