The Gateway to Computer Science Excellence
0 votes



$L_{26}=\{<M>|$ M is a TM such that both L(M) and $\lnot L(M)$ are infinite $\}$

I was unable to get proof given in pdf above.Can anyone explain, if someone got it.

in Theory of Computation by Boss | 90 views

Say, $M_1=\left \{a^n:n\,\,is\,\,a\,\,multiple\,\,of\,\,2\right \}$

$\overline{M_1}$ will be strings where n will not be multiple of 2

So, both $M_1$ and $\overline{M_1}$ are infinite. So, $L(M_1)=T_{yes}$

$M_2=\left \{a^n:n\geq 0\text{}\right \}$


So, $M_1$ is infinite but $\overline{M_1}$ is not. So, $L(M_2)=T_{no}$

So, $T_{yes}\subset T_{no}$  as  $M_1\subset M_2$

So, it is a non-monotonous property. Hence non-RE

Correct me if I'm wrong


@Shobhit Joshi-Seems good to me :).But I can't detect any flaw here so be cautious.

Works almost all the time, let's see if it works in gate !
Can I take the machine M2 to be the machine that accepts everything?
it accepts every string of length >= 0, using only $a$

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,215 questions
59,981 answers
94,633 users