patternMinor
Language of TMs that accept some x in less than 50 steps. Is it in co-RE?
Viewed 0 times
tmsacceptthanlanguagethatsomelesssteps
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#68534, answer score: 3
Revisions (0)
No revisions yet.