# A reformulation of reducibility

I found the theory of computation books very imprecise about their descriptions of Turing machines and reductions. They usually start with something precise and mathematical, for example they would define a Turing machine as a 7-tuple, but after that, everything about decidability and reduction is described with impenetrable paragraphs in natural languages.

I believe that the use of natural languages leads to most of the confusion in theory of computation because natural languages are inherently imprecise and ambiguous. There are too many ways to say the same thing. For example, you can find these sentences which mean exactly the same in the books:

- “Run M on w”
- “Run M on input w”
- “Simulate M on w”

The pronouns and references are even more confusing. For example:

“Use the description of M and w to construct the TM M

_{1}justdescribed.”

What is “just described”, and do M and w here mean the same things as in the earlier paragraph?

Another serious problem is that natural languages are very weak at representing the notion of “interpretation”, which underlies much of theory of computation. For example, a Turing machine simulates another Turing machine, which again contains and simulates yet another one.

After some thought, I found that we could use something precise such as mathematical notations combined with programming languages to describe the concepts. As an example, I’ll show here how the notion of reduction can be defined precisely as a homomorphism which can be instantiated for reducing one problem to another.

**Definition 1** (reduction): A *reduction* (as in theory of computation) is a homomorphism (as in universal algebra):

Reduce(TM, I) = (TM', I')

satisfying the property

TM @ I = TM' @ I'

where

`TM`

= Turing machine which we reduce from`TM'`

= Turing machine which we reduce to`I`

= input string of TM`I'`

= input string of TM’`@`

= simulation, similar to the Scheme code`((eval TM) I)`

`TM @ I`

= result from simulating TM on I (accept or reject)`TM' @ I'`

= result from simulating TM’ on I’ (accept or reject)

End of Definition 1.

Notice that the simulation `(TM @ I)`

may go into an infinite loop and never produce any result. Now I show how to use this homomorphism to describe the reduction from ATM ==> HALT, where

`ATM`

= the “acceptance problem” (deciding whether a Turing machine M accepts string w)`HALT`

= the “halting problem” (deciding whether a Turing machine M halts on string w)

For convenience, we let

`D`

= “the decider of ATM”_{ATM}`D`

= “the decider of HALT”_{HALT}

Now the reduction can be fully described by the following homomorphism:

Reduce(D_{ATM}, (M,w)) = (D_{HALT}, (M',w)) where M' = <if (M @ w) then accept else loop> satisfying D_{ATM}@ (M,w) = D_{HALT}@ (M',w)

Yes, that’s an all-inclusive formal proof that `HALT`

is undecidable. It even includes the notion of “reduction” itself.

Let me explain it a bit. The first line says that there exists a function (named `Reduce`

) from the pair `(D`

to another pair _{ATM}, (M,w))`(D`

, where _{HALT}, (M',w))`M' = <if (M @ w) then accept else loop>`

is a description of a Turing machine.

Now let’s look at the last line:

D_{ATM}@ (M,w) = D_{HALT}@ (M',w)

It says: if we have a decider for `HALT`

(`D`

), then we can use it to define _{HALT}`D`

, thus deciding _{ATM}`ATM`

.

Why this is a valid defintion for `D`

? This is because from the definition of _{ATM}`M'`

<if (M @ w) then accept else loop>

we know that:

- If
`(M @ w)`

accepts,`M'`

accepts, thus`D`

accepts_{HALT}@ (M',w) - If
`(M @ w)`

rejects,`M'`

loops, thus`D`

rejects_{HALT}@ (M',w) - If
`(M @ w)`

loops,`M'`

loops, thus`D`

rejects_{HALT}@ (M',w)

Notice from the colored words that `D`

will accept if and only if _{HALT} @ (M',w)`M`

accepts `w`

. Thus this defines a decider for `ATM`

.

So if `D`

exists, then we can have _{HALT}`D`

. But this contradicts the fact that _{ATM}`D`

cannot exist, so _{ATM}`D`

must not exist._{HALT}

If you wonder how this proof corresponds to Definition 1, here is some details how it is instantiated:

`TM = D`

(nonexistent)_{ATM}`TM' = D`

(hypothetical)_{HALT}`I = (M,w)`

where`M`

is the description of a Turing machine which we want to know whether it accepts input w.`I' = (M',w)`

where`M'`

is`<if (M @ w) then accept else loop>`

`TM @ I = D`

(running decider of_{ATM}@ (M,w)`D`

on input_{ATM}`(M,w)`

)`TM @ I' = D`

(running decider of_{HALT}@ (M',w)`D`

on_{HALT}`(M',w)`

)

This is a lot more concise, accurate and easier to understand than a paragraph:

F = "On input <M,w>: 1. Construct the following machine M' M' = "On input x: 1. Run M on x. 2. If M accepts, accept. 3. If M rejects, enter a loop." 2. Output <M',w>."

- Posted in: programming languages ♦ theory of computation