0
$\begingroup$

Consider an algorithm that accepts a Turing Machine M and constructs another Turing machine M2, such that L(M) $\neq$ L(M2). Show that such algorithm cannot exist.

My answer: If such algorithm exist, we could tell whether a Turing machine M accepts input w or not, as follows:

Construct a Turing machine X:

X receives input z   if z equals 1      run M on input w      if M accepts w         X accepts z 

Now we use the claimed algorithm to create machine X' that accepts a language different from L(X)

if M accepts w, the language of X is 1 and the language of X' is all strings, but 1

if M does not accept w, the language of X is every string in $\Sigma ^*$, but 1; and the language of X' is just 1

L(X) and L(X') complement each other

run both X and X', in parallel, on input 1 if X  accepts 1, then M accepts w if X' accepts 1, then M does not accept w 

We have solved an undecidable problem: the halting problem; thus contradicting the hypothesis of the existence of such algorithm.

Is this correct?

Thanks!

[Edited] As @mjqxxxx pointed out, my assumption that L(X') is the complement of L(X) is wrong. The problem only states that L(X') $\neq$ L(X).

Any hints on how to approach this proof?

  • 0
    @mjqxxxx, you are correct. if L={a}$A$could generate a TM for {a,b}. Thanks! Any hints on how to approach this proof?2012-06-21

1 Answers 1

3

I'm assuming that $L(M)$ means the set of inputs on which $M$ terminates.

What you need here is a diagonalization argument. Such arguments are easiest to construct if we assume that every program may use its own source code as data, and I'll present the argument in that way first.

Suppose we have an (always terminating) algorithm $A$ which for every machine$M$ produces a different program $M'$ such that $L(M)\ne L(M')$. Now construct a new machine $T$ as follows:

T does:    Read input X    Let U = A(T)    Simulate U on input X    Return the output from U 

Since $U$ does not depend on the input $X$, it is the same for every run of $T$. Also, clearly $L(T)=L(U)$ because all $T$ does is to run $U$. However, if $A$ works as assumed then $L(U)\ne L(T)$, which is a contradiction, so $A$ cannot exist. Q.E.D.

The only gap in this argument is the assumption that $T$ is able to run $A$ on its own description. $T$ cannot just naively contain its own source code as a constant, because then the source code would need to be larger than itself. The way around this problem is to use one of the many quine techniques when writing $T$.

The classical diagonalization looks a bit more algebraic and mathematically "dignified" but is essentially just a particular quine construction. Here we start by constructing a machine $D$:

D does:   Read inputs P, X   Construct a machine Q that does:      Read input Y      Simulate P on input P, Y      Return the output from P   Let U = A(Q)   Simulate U on input X   Return the output from U 

Once we have this $D$, we can construct $T$:

T does:    Read input X    R = D(D,X)    Return R 

It is then easy to see that $T$ does exactly the same as the $Q$ that $D$ constructs when it is called, so this new program is essentially the same as the earlier self-referential one.

If you're familiar with the lambda calculus, you may also observe that the workings of this construction are very similar to the Y combinator.