# Tag Info

## Hot answers tagged semi-decidability

1

$L = \{\text{<M, k>| M is a Turing Machine and } |w \in L(M) : w \in a^*b^*| \geq k \}$ Now we want to find whether $L$ is $RE$ or not. Yes, indeed your interpretation of language $L$ is wrong. $L$ is a language of strings of form $\langle M, k \rangle$ where $M$ is turing machine which accepts atleast $k$ strings of form $a^*b^*$. So, now it's ...

1

A language is Turing decidable if you can write a C program (replace C with your favorite programming language) that outputs YES if the input belongs to the language and outputs NO otherwise. It is Turing recognizable if in the latter case the C program simply never halts.

Only top voted, non community-wiki answers of a minimum length are eligible