L = {M | M is a TM and there exists an input that the TM M accepts in less than 50 steps}

I need to find a minimal class it belongs to between R/ RE/ co-RE/ not in RE∪co-RE. I managed to show that it is in RE with a TM. I think its not in co-RE, because it has to check every input to know wheter a TM M belongs to L. and there are an infinite amount of inputs. I tried to use mapping recursion with ATM, but that failed. Would appreciate any advice, thanks.

  • $\begingroup$ Hint: If it s both RE and co-RE then it is recursive. $\endgroup$ – Yuval Filmus Jan 10 '17 at 21:00
  • $\begingroup$ By intuition I think its not in co-RE. Because to know that for every input x, M does not accept x in less than 50 steps, we have to run it for every x and check. But if we run 50 steps for every input, and one that accepts in less than 50 steps does not exists, we will continue forever. Why is that not correct? $\endgroup$ – Gray Jan 10 '17 at 21:34
  • 1
    $\begingroup$ Try to use my hint. Intuition is not enough. $\endgroup$ – Yuval Filmus Jan 10 '17 at 21:42
  • 3
    $\begingroup$ @Bar : In 50 steps, you can't read more than $50$ letters of the input so.... $\endgroup$ – xavierm02 Jan 10 '17 at 22:15
  • 1
    $\begingroup$ @Bar : If two inputs have the same 50 characters, then ... so you only need to test ... different inputs. $\endgroup$ – xavierm02 Jan 11 '17 at 9:15

Maybe that will help ?


Page 42 Credits : Nancy Lynch MIT

Applications of Rice’s Theorem

• Example 3: Another property that isn’t a language property and is decidable

{ M |M is a TM that runs for at most 37 steps on input 01 }

– Not a language property, not a property of a machine’s structure.

– Rice doesn’t apply.

– Obviously decidable, since, given the TM description, we can just simulate it for 37 steps.

  • $\begingroup$ Please transcribe the slide as text, to make textual search possible. $\endgroup$ – Yuval Filmus Jan 12 '17 at 9:58

Your problem is decidable, since a Turing machine accepts some input in $t$ steps iff it accepts some input of length at most $t$ in $t$ steps, and the latter property can be easily checked.

Repeating my comment, if you aimed at proving a negative answer, one avenue would be to prove that the language is not recursive; since you already know that the language is recursively enumerable, it would follow that it is not co-recursively enumerable.

Stated succinctly, an r.e. language is recursive iff it is co-r.e.


This is my solution:

reduction from ATM to L

On input M,w: return a machine M', that on input x: runs w on M, and if M accepts, M' accepts(in a single step) if M decline or loops, decline

if M accepts w, L(M')=Sigma* and therefore is y in Sigma* that M' accepts in a single step(in fact it's true for all y in Sigma*)-that's less 50. if M loops or declines, L(M')=emptyset and therefore there is no word the M' accepts in less than 50 steps, because M' rejects all words.

good luck on your hw!

  • $\begingroup$ This is a reduction from L to ATM (when you say "run w om M and, if M accepts, ..." I think you mean "uses the oracle for ATM to determine in a single step whether M accepts w". You need to explain how showing a reduction from L to ATM addresses the question of whether L is co-RE. $\endgroup$ – David Richerby Jan 14 '17 at 16:19
  • $\begingroup$ It's a mapping reduction, not a turing reduction $\endgroup$ – jon Jan 21 '17 at 10:59

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.