2022 Developer Survey is open! Take survey.

# Tag Info

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 ...

• 33.1k
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