Questions tagged [semi-decidability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
2answers
253 views

Is it possible to obtain a total function by composition of partial functions?

This statement is Theorem 1.1 (page 39) of Computability, Complexity and languages by Martin Davis: If function $h$ is obtained from the (partially) computable functions $f$, $g_1$, $g_2$, ..., $...
2
votes
1answer
105 views

Is there a class of formal grammars that generate Recursive Languages only?

Is there a class of formal grammars that generate Recursive Languages only? (ie with which it is not possible to generate non recursive languages.) If so what kind of production rules/restrictions do ...
0
votes
2answers
2k views

Can languages with infinite strings be recursively enumerable?

I am not 100% sure about the definition of recursively enumarable languages. Yes I know how are they defined: There has to exist a Turing machine that accepts all wrods of the language and halts but ...
0
votes
2answers
596 views

Extension of Rice's theorem

How can one prove that every nontrivial property of pairs of semi-decidable sets is undecidable? (This is an extension of Rice's theorem that "Every nontrivial property of the r.e. sets is undecidable"...
1
vote
1answer
106 views

Clarification of Hopcroft's proof that “deciding whether a program halts on all inputs” is not R.E

$DoesNotHaltOn\_w=\{(M, w) : M$ does not halt on input w$\}$ $AlwaysHalt =\{ M : M$ halts on all inputs x $\}$ Hopcroft gives the following proof that $AlwaysHalt$ is not R.E. 1) Given an input ...
1
vote
1answer
463 views

Examples for incomparable semi-decidable but undecidable languages

In Schönig and Pruim's Gems of Theoretical Computer Science, the following statement is made: 'Post's Problem', as it has come to be known, is the question of whether there exist undecidable, ...
0
votes
0answers
142 views

Can we recognize wheter a Turing machine is a decider? [duplicate]

Let $L=\{ \langle M \rangle \mid M \text{ is a Turing Machine which halts on all inputs}\}$. Is this a Turing-recognizable language? I guess that it is neither Turing-recognizable, nor co-Turing-...
4
votes
1answer
4k views

Can you recognize or decide if a Turing Machine has an infinite sized language?

That is, can you build a Turing Machine that, if given a Turing Machine as input, can decide (or at least recognize) if the inputted Turing Machine has an infinite number of strings in its language? ...
2
votes
1answer
1k views

Is there C++ code that takes infinite time to compile?

Is C++ as a formal language recursively enumerable? If yes, is there any invalid C++ code that takes "infinite" time to compile?
1
vote
1answer
274 views

Proving that context-freeness of $L(M)$ is not semi-decidable using Rice's theorem

This is a question from an exam I did today: Given $M$, a turing machine, we need to decide the following: 1) $M$ halts on every input 2) The language of $M$ is CFL My question is, can I ...
7
votes
2answers
2k views

Is it possible for a language and its complement to both be unrecognizable?

Given some unrecognizable language $L$, is it possible for its complement $\overline{L}$ to also be unrecognizable? If some other language $S$ and its complement $\overline{S}$ are both recognizable, ...
3
votes
2answers
9k views

Why is the class of recursively enumerable languages not closed under complementation?

I am having a hard time understanding closure properties of recrusively enumerable languages. I have read the explanation on this site but still unable to fully understand why they are not closed ...
1
vote
1answer
404 views

Is the set of Gödel numbers of computable constant functions recursively enumerable?

I've been working on the following exercise: $S = \{ x | f_x \text{ is constant} \}$. Is $S$ recursively enumerable? Here, $fx$ is the function computed by the $\text{x-th TM}$. So it is a ...
3
votes
1answer
390 views

Show that a language is RE or recursive

Consider these 2 languages: $L_{\ge5} = \left \{ \left< M \right> : M \text{ accepts at least 5 strings} \right\} $ $L_{<5} = \left \{ \left< M \right> : M \text{ accepts fewer ...

1 2 3 4