New answers tagged computability
5
votes
Accepted
Sets of problems in different models of computation and cardinality
Cardinality is a Weak Property
As described in the question, cardinality is a very weak property. It is not strong enough to distinguish $s(FSM)$, $s(PDA)$, $s(TM)$. It cannot differentiate any two ...
- 33.1k
1
vote
Accepted
Are all Scott-continuous functions computable?
$\newcommand{\TM}{T\!M}$
Let $\TM$ be the set of Turing machines and $2 = \{0,1\}$.
The powerset of any set with $\leq$ equal to $\subseteq$ is a CCPO, its least upper bounds being the unions of the ...
2
votes
Is the problem of "DFA-TM-INCLUSION" recursively enumerable?
TOTAL is the problem of deciding whether a given Turing machine halts on all inputs. This problem is $\Sigma_2$-complete, and in particular, it is neither r.e. nor co-r.e.
Your problem is also $\...
- 269k
2
votes
Accepted
Is the problem of "DFA-TM-INCLUSION" recursively enumerable?
No, $\{\langle D,M\rangle\mid D\text{ is a DFA }\land M\text{ is a Turing Machine }\land L(D)\subseteq L(M)\}$ is not recursively enumerable.
Let $Z=\{0^{n}\mid n\ge0\}$. Call a Turing Machine (TM) $...
- 33.1k
8
votes
Accepted
How do we check $x ≠ y$ in $PDA$ for $L = \{xy | x, y \in (0 + 1)^*, |x| = |y|, x ≠ y\}?$
If two strings $w_1, w_2$ of the same length are different from each other, then you can find a specific position where they differ:
$$w_1 = \underbrace{\square\ldots \square}_{k\text{ symbols }}\;x\;\...
- 738
1
vote
What are some examples of non-enumerable languages whose complement isn't either?
A random language is neither recognizable nor co-recognizable almost surely.
Every language which is complete for $\Sigma_k$ or $\Pi_k$, for any $k \geq 2$ (these are classes in the arithmetical ...
- 269k
1
vote
Accepted
Whose fault is that $\mathsf{\text{NOT-HALT}}$ is not in $\mathsf{RE}$?
It's the prover's fault: there is no way to decide whether an arbitrary TM will halt or run forever, and so there is no certificate to prove that an arbitrary TM will run forever.
If $L$ is not ...
- 738
4
votes
Accepted
DFA for the language of non-empty words that are no longer than $2^6$
Suppose the minimal DFA $(Q, \delta, q_0, F)$ contains strictly less than $2^6$ states. Then there exists a state $q$ and two words $u$, $v$ such that $|u| < |v| \leqslant 2^6$ and $\delta(q_0, u) =...
- 7,154
3
votes
Accepted
Proving Undecidability of this Language
Fix $i$ and $j$ as two positive integers, as per your comment.
Consider the language $H$ containing all pairs $\langle T, y\rangle$ where $T$ is (encoding of) a Turing machine, $y \in \Sigma^*$, and $...
- 22.7k
Top 50 recent answers are included