Archive | Computation Theory

# Demystifying Turing Reductions

Among the many computation theory topics that seem completely inexplicable are Turing Reductions. The basic idea here is that there are certain problems that have been proven to be unsolvable. Given that these problems exist, we can prove other prove that other problems are unsolvable by reducing these problems to a known unsolvable problem.

## Turing Machines?

A Turing Machine is a theoretical device. It has an infinitely long tape, divided up into cells. Each cell has a symbol written on it. The Turing Machine can do a few things with this tape: it can read from a cell, write to a cell, move the tape one cell to the left, or move the tape one cell to the right. If the Turing Machine tries to move the cursor off the left side of the tape, the head won’t move. Additionally, the Turing Machine can halt and accept or reject. A Turing Machine has a starting configuration: the tape head begins on the leftmost end of the tape, and the tape has an input written on it.

What the Turing Machine does is implementation specific; one Turing Machine may accept a different input than another. This implementation has a mathematical definition, but we care about the high level definition, that looks similar to this:

``````M = "On input w:
2. If the cell is not blank, accept
3. If the cell is blank, output "Was empty"
onto the tape then reject"``````

This Turing Machine will accept if there is something written on the tape. If the tape is initially empty, it will write “Was empty” onto the tape and reject. This Turing Machine is a decider because it always halts (I.E. has no infinite loop). We say that the Language of M is the set of all non-empty strings, as it accepts all inputs except the empty string. As you can see, this looks very much like a function written in a programming language. I could implement this in Haskell:

``````m :: String -> (String, Bool)
m "" = ("Was empty", False)
m w = (w, True)``````

Consider the following Turing Machine:

``````M = "On input w:
1. Move the head to the leftmost tape cell.
3. If the cell is blank, accept
4. If the cell is not blank, move the head one cell to
the right
5. Go to step 2"``````

This Turing Machine will accept all inputs including the empty string. It’s language is the set of all strings. In Haskell, this might look like this:

``````m :: String -> Bool
m "" = True
m (c:w) = m w``````

Spot the bug? What happens if we call this on an infinite list?

``m ['a'..]``

That’s right, infinite recursion. Despite the bad implementation, this is still a valid Turing Machine. We call this a recognizer. It halts on all inputs that are in the language, and it either halts and rejects, or doesn’t halt on all inputs not in the langauge. A language is decidable if there is a decider for it.

## Decidability is Undecidable

Much like higher-order functions in programming, Turing Machines can be used as the input to other Turing Machines. Take the following:

``````A_TM = "On input <M, w> =
1. If M is not the encoding of a Turing Machine, reject
2. Simulate M on w, if M accepts w accept. If M rejects
w, reject``````

This very simple Turing Machine accepts the encoding of a Turing Machine, and a string, and if the types are right, returns the result of running the machine on the string. In Haskell:

``````aTM :: (String -> (String, Bool))
-> String -> (String, Bool)
aTM m w = m w``````

Seems straight-forward enough; A_TM takes a Turing Machine, and a string and runs them. This is a recognizer because all Turing Machines are at least recognizers, but is it a decider? To figure that out, we need some more tooling.

Much like in programming, if function `a` calls function `b`, and `b` might infinitely loop, then `a` can also infinitely loop. But let’s suppose we have a function that can take a function as an argument, and get its result, that is guaranteed to never infinitely loop:

``````alwaysReturns :: (String -> (String, Bool))
-> String -> (String, Bool)
alwaysReturns f arg = -- Magic``````

It doesn’t matter how this function is implemented, it just magically can get the result of calling `f` with `arg` and it will return the correct result 100% of the time, without running it. We can think of it as some perfect static analysis tool. What a world, right? Now suppose I wrote the following function:

``````negate :: (String -> (String, Bool)) -> (String, Bool)
negate f = (result, (not accRej))
where
(result, accRej) = alwaysReturns f (show f)``````

Ignoring the fact that functions don’t have `Show` instances, let’s see what’s going on there. The function `negate` takes a function as an argument, and calls `alwaysReturns` on the function, and with `show`‘d function as its argument. `negate` then negates the accept/reject result and returns the opposite. In other words, if `alwaysReturns f (show f)` returns `(result, True)`, then `negate` returns `(result, False)`. This function will never infinitely loop thanks to `alwaysReturns`. So, what happens if I do this?

``negate negate``

Let’s follow the logic: `negate` delegates to `alwaysReturns`, which does stuff, then returns the result of `negate negate`. Next negate returns the opposite of what `alwaysReturns` said it would. Thus, `alwaysReturns` did not correctly determine the output of `negate`. Because of this example, we can definitively know that a function that always correctly decides another function can’t exist. Thus there is at least one Turing Machine that is not decidable, and A_TM cannot be a decider.

## So, How About Those Reductions?

Now that we have that all out of the way, let’s talk reductions. It was a bit convoluted, but we’ve proven that the decidability of Turing Machines is undecidable. How can we use this? It turns out that we can use this to prove other problems undecidable. Let’s use my Turing Machines as functions idea to talk about some other undecidable problems.

#### If a TM Halts is Undecidable

Suppose we had the following function:

``````alwaysHalts :: (String -> (String, Bool)) -> Bool
alwaysHalts f = -- Magic``````

This function returns True if the passed-in function will never infinitely loop. If this function existed, then we could implement a function to decide any Turing Machine:

``````perfectDecider :: (String -> (String, Bool))
-> String -> (String, Bool))
perfectDecider f w
| alwaysHalts w = f w
| otherwise = (w, False)``````

This function first tests to see if it’s safe to call `f`, and if so, returns `f w`. If it’s not safe to call `f`, it just returns `(w, False)`. However, we already proved that this function couldn’t exist, so the thing that makes it possible must also be impossible.

Suppose we had a Turing Machine `R` that is an implementation of `alwaysHalts`, that accepts all Turing Machines over `<M, w>` that halt. The Turing Machine language implementation of `perfectDecider` would look like this:

``````M = "On input <M, w>:
1. Simulate TM R on <M, w>, if R rejects, reject
2. Simulate M on w. If M accepts, accept.
If M rejects, reject``````

As you can see, the logic is similar. We run `R` on `<M, w>`. If `R` rejects, that means that `M` didn’t halt, so we reject. Otherwise we return the result of running `M` on `w`.

#### If the Language of a TM is empty is undecidable

Suppose we had the following function:

``````lIsEmpty :: (String -> (String, Bool)) -> Bool
lIsEmpty f = -- Magic``````

This function will return True if the language of the provided function is empty, and False if not. Similar to the halting problem above, we want to implement `perfectDecider`. But how would we do that?

``````perfectDecider :: (String -> (String, Bool))
-> String -> (String, Bool))
perfectDecider f w = not (lIsEmpty emptyAsReject)
where
emptyAsReject w' =
if (w' == w)
then f w'
else False``````

So, what’s going on here? We have a function that can decide if the language of a TM is empty. So if we want to construct a decider using this, we need to exploit this property. We write a closure that has this property. The function `emptyAsReject` rejects any string that does not equal `w` automatically. Then, it runs `f w'`. Thus, if `f` rejects `w'`, then the language of `emptyAsReject` is empty. otherwise it contains the single string `w`. Thus we treat the empty set as False, and anything else as True.

We can use this method to prove any arbitrary problem undecidable.

#### {<M> | M is a Turing Machine, and the language of M is {“happy”, “time”, “gatitos”}} is undecidable

In the culmination of this long-winded post, we’ll prove that it is undecidable if a Turing Machine’s language is {“happy”, “time”, “gatitos”}. As before, we’ll assume we have the following function:

``````lIsHappyTimeGatitos :: (String -> (String, Bool)) -> Bool
lIsHappyTimeGatitos f = -- Magic``````

We’ll use this to solve the ultimate problem in computer science!

``````perfectDecider :: (String -> (String, Bool))
-> String -> (String, Bool))
perfectDecider f w = lIsHappyTimeGatitos hgtAsAccept
where
hgtAsAccept "happy" = True
hgtAsAccept "time" = True
hgtAsAccept "gatitos" = f w
hgtAsAccept _ = False``````

Here, we construct a closure that has the desired property language if `f` accepts `w`, and does not have the desired language if `f` rejects `w`. `hgtAsAccept` always accepts “happy” and “time”, but only accepts “gatitos” if `f w == True`. Thus, if `f` does not accept `w`, then `lIsHappyTimeGatitos` will reject `hgtAsAccept`, and vice versa.

## Well, When You Put It That Way…

Math is nice and all, but we’re programmers. I feel that this is a concept that is not that hard, but when math runes get involved, things get difficult. I think you can see how this works, and grasp the concept. Thinking of these reductions as functions helped me, and I hope it helps you too.