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

Is $$L=\{ | 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 \ 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 ?

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 $$$$)

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!)

• I dont understand your solution. I think if I edit the third step from my solution it should be fine, right ? I would edit step 3 to this: If m loops or reject construct a TM Mwhich accepts everything. Return M – Frank Jul 17 at 11:14
• You can't know whether something loops or not - thats the halting problem, and as we all know - its not decidable! – nir shahar Jul 17 at 11:15
• Could maybe provide the solution to your given answer ? I am not able to solve it. – Frank Jul 22 at 9:05