0
$\begingroup$

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 ?

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Frank Jul 17 at 11:14
  • $\begingroup$ You can't know whether something loops or not - thats the halting problem, and as we all know - its not decidable! $\endgroup$ – nir shahar Jul 17 at 11:15
  • $\begingroup$ Could maybe provide the solution to your given answer ? I am not able to solve it. $\endgroup$ – Frank Jul 22 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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