Cheap and Secure Web Hosting Provider : See Now

[Solved]: Proving that a language is not Recursive

, , No Comments
Problem Detail: 

I have the following language:

T = {M | there exists w such that M accepts w within |w| steps}

I am trying to prove that this language is not recursive and that it is recursive-enumerable. To prove that it is NOT recursive I considered the following steps:

1) Assume that it was recursive 2) Conside input w of infinite length 3) Meaning, we get infinite steps that M can perform before halting. So we get the halting problem when considering this infinite input, and we are saying that we can decide it 4) halting problem is not decidable. contradiction

What do you think about this proof? I'm not sure that I can consider an infinite length input, and I'm not sure wither turing machines in general should deal with infinite inputs lengths.

I tried to search for answers with no luck so far. Any help would be much appreciated. Thanks.

Asked By : Hanna

Answered By : Shaull

Proving that the language is in RE is quite easy: simulate the machine on every input $w\in \Sigma^*$, in minlex order, for $|w|$ steps. If an input is accepted - accept.

Proving that the language is undecidable can be done by reduction from $$A_{TM}=\{<M,w>: M\text{ accepts }w\}.$$ A possible reduction:

Given input $<M,w>$, construct a new TM $M'$ that works as follows: given input $x$, simulate $M$ on $w$. If $M$ accepts, accept. If $M$ rejects, reject, and of course if $M$ does not halt then so will $M'$.

Now, if $<M,w>\in A_{TM}$, then $M$ accepts $w$ within $t$ steps, for some $t\in \mathbb{N}$. Thus, for a word $x$ with $|x|>>t$ (the size of $|x|$ needed depends on the manner of simulation, but can be done with $O(t\log t)$), the simulation of $M$ on $w$ will terminate within $|x|$ steps, and $M$ will accept $w$, so $M'$ will accept $x$, and $<M'>\in L$.

Conversely, if $<M,w>\notin A_{TM}$, then $M'$ will not accept any input, so $<M'>\notin L$, and you are done.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47214

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback