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: 1. Read the first cell. 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. 2. Read from the 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.

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

%d bloggers like this: