2022 Developer Survey is open! Take survey.

New answers tagged

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 ...
user avatar
  • 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 ...
user avatar
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 $\...
user avatar
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) $...
user avatar
  • 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\;\...
user avatar
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 ...
user avatar
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 ...
user avatar
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) =...
user avatar
  • 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 $...
user avatar
  • 22.7k

Top 50 recent answers are included