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.

Let $\alpha_1$; $\alpha_2$ be any two different finite binary strings. Let $E_{\alpha_1\alpha_2}$ be the set of all codes of programs M such that M does not distinguish between the input $\alpha_1$ and the input $\alpha_2$. That is, if M halts on one of these inputs, it halts on the other as well, and in that case, M($\alpha_1$) = M($\alpha_2$). Prove that the decision problem defined by $E_{\alpha_1\alpha_2}$ is not decidable.

I think I can prove that it's undecidable using the halting problem but I am not sure how to use it. What is a general method to solve these types?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Reduction. That is almost always the method that we use. Details of the reduction process differ, depending on the problem. But we almost always show that if there were an algorithm for our specific kind of problem, then we could use that algorithm as a subroutine to produce an algorithm that solves the Halting Problem.

Define machine $M_n$ as follows. Given input $0$, $M_n$ produces output $111$ and halts. Given any other input, such as $1$, $M_n$ produces the number $n$, then imitates the behaviour of a universal Turing machine on input $(n,n)$, except that if it halts, it produces output $111$. The index of $M_n$ is a recursive function of $n$.

If we had a general algorithm for determining whether a machine has the same halting behaviour on inputs $0$ and $1$, we could apply it to the machines $M_n$, and have an algorithm for determining whether a universal Turing machine halts on input $(n,n)$. However, the usual diagonalization argument shows that there is no such algorithm.

share|improve this answer
    
"The index of Mn is a recursive function of n." I don't quite understand this part. –  Mark Aug 3 '11 at 5:51
    
By index of a TM I mean any one of the standard ways to assign a positive integer to a TM. Call the TM with index $k$ by the name $T_k$. I am saying there is a recursive (Turing computable( function $f(n)$ such that $M_n$ is machine $T_{f(n)}$. More informally, there is an algorithm for checking whether a machine is one of our $M_n$. –  André Nicolas Aug 3 '11 at 6:36

The general produce of proving that something is undecidable is finding a function $f$ that reduces the halting problem (or any undecidable problem you know) to your problem, which has the following property

$$M,x \in HALT \Leftrightarrow f(M) \in E_{a_1,a_2} $$

Let's now create this function

begin f: on input M,x

  • Create a program M': on input y

    • if M(x) halts check whether y = a_1 or a_2, if so output yes
    • else if $y = a_1$ output yes
    • else if $y = a_2$ output no
  • output M'

end f

Clearly, we should prove that this reduction actually works, this however, should not be to hard for you, as I constructed M' so that it outputs yes for $a_1$ and $a_2$ if M(x) halts, and made their outputs different if M(x) does not halt.

EDIT: Had a fundamental flaw in my property of $f$, but this is fixed now, sorry it is late!

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.