5
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ Hint: If it s both RE and co-RE then it is recursive. $\endgroup$
    – Yuval Filmus
    Commented Jan 10, 2017 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$
    – Bar
    Commented Jan 10, 2017 at 21:34
  • 1
    $\begingroup$ Try to use my hint. Intuition is not enough. $\endgroup$
    – Yuval Filmus
    Commented Jan 10, 2017 at 21:42
  • 3
    $\begingroup$ @Bar : In 50 steps, you can't read more than $50$ letters of the input so.... $\endgroup$
    – xavierm02
    Commented Jan 10, 2017 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
    Commented Jan 11, 2017 at 9:15

3 Answers 3

Reset to default
3
$\begingroup$

Maybe that will help ?

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec09.pdf

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Please transcribe the slide as text, to make textual search possible. $\endgroup$
    – Yuval Filmus
    Commented Jan 12, 2017 at 9:58
2
$\begingroup$

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.

Improve this answer
$\endgroup$
-1
$\begingroup$

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!

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jan 14, 2017 at 16:19
  • $\begingroup$ It's a mapping reduction, not a turing reduction $\endgroup$
    – jon
    Commented Jan 21, 2017 at 10:59

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.