Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
migrate to cstheory.stackexchange.com ? –  leonbloy Jun 21 '12 at 17:10
    
Theorem of rice? –  FUZxxl Jun 21 '12 at 17:11
    
Note, you say "consider the algorithm..." But you don't describe an algorithm, you describe a condition on an algorithm, a condition which you are showing cannot be met. –  Thomas Andrews Jun 21 '12 at 17:12
1  
This is essentially the Second Kleene recursion theorem: en.wikipedia.org/wiki/Kleene%27s_recursion_theorem . –  Thomas Andrews Jun 21 '12 at 17:15
3  
No, this isn't correct; the assumption is (essentially) that there's a computable function $A$ that maps Turing machines to Turing machines, such that $L(A(M))\neq L(M)$ for all $M$. You're using a stronger assumption, which is that $L(A(M))=L(M)^{c}$ (i.e., that $A(M)$ accepts exactly those strings that $M$ fails to accept). –  mjqxxxx Jun 21 '12 at 19:15

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.