$FINITE_{TM} = \{\langle M \rangle\mid M\text{ is a TM and }L(M)\text{ is finite}\}$

$A_{MT} = \{\langle M,w \rangle \mid M\text{ is a TM and }M\text{ accepts }w\}$

I'm trying to prove that $FINITE_{TM}$ is not Turing-reducible to $A_{MT}$ by contradiction.

Supposing it is, I get that there's an oracle Turing machine $H^x$ that decides $FINITE_{TM}$ for $x = A_{MT}$, but I have no idea how to reach a contradiction using this.


1 Answer 1


Point: For simplicity we work with TM whose language contains only numbers.

Let's say FINITE is Turing reducible to A.

INFINITE = { (M) | M is a TM and L(M) is infinite}

Then we can make a TM with an oracle for A say M which can enumerate all members of INFINITE. Let the following sequence be our enumeration:

e1 e2 e3 .....

This sequence enumerates all Turing machines with an infinite language.

Consider this machine:((Call it NM))

1- Initiate i = 1.

2- print i'th least member of ei's language plus 1. ((To do this step we use an oracle for A))

3- increase i once.

4- go to 2.

This machine cannot be appeared in our enumeration of INFINITE's members because otherwise if ek is NM's code, Then we should have that k'th least member of L(NM) plus 1 equals to k'th least member of L(NM)!

But the language this machine recognizes is infinite, So it belongs to INFINITE. Which contradicts the fact that our enumeration contains all TMs with infinite language.

So no TM with an oracle for A can enumerate members of INFINITE. So FINITE is not Turing reducible to A.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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