Is the languague L={<M>, M accepts a finite amount of words} decdidable?

Question

Is $L=\{<M> | L(M) \ is \ finite\} $ decidable ? M is a TM.

I think its relative simple to proof with the theorem of rice. But I am interested in a solution which does not use the Rice theorem.

This my try : Let f(<m,w>) be a function which works in the following way :

1. Run w on M
2. If M accepts Construct a TM Mwhich accepts only the word w and return M
3. If M rejects Construct a TM Mwhich accepts everything. Return M

So if m is in $A_{TM}= \{<M,w>|M \ accepts \ w\}$ we know that f(<m,w>) is in L. If m is not in A then we know that f(<m,w>) does accept every word and therefore infinity words. So f(<m,w>) not in L.

Is this a correct mapping reduction ?

Answer 1

The function you defined is not a reduction at all - it may not even stop!

The problem is running $m$ on $w$: can you be sure $m$ wont be stuck in an infinite loop on $w$? you can't.

You can define a proper reduction as follows: (on input $<m,w>$)

Create the machine $M_{m,w}$that does the following algorithm, and return in: (on input $s$)

1. Emulate $m$ on $w$ for $|s|$ steps. If $m$ halted in that time, reject $s$. Otherwise, accept $s$.

I will leave it for you to prove this is a proper reduction from $H_{TM}$ to $L$ (its a good exercise!)