New answers tagged computability
10
votes
Are any two recursive languages reducible to one another?
This is almost true, with the only exception being trivial languages: ($\Sigma^*$ and $\emptyset$).
Note that the claim can be made stronger: you don't even need $B$ to be decidable (i.e., recursive).
...
- 17.6k
1
vote
Accepted
How to proof the existence of languages over {0,1}* that are neither semi-decidable nor co-semi-decidable
An usual example is the language:
$$\mathsf{ALL} = \{\langle M\rangle \mid \forall x\in \{0,1\}^*, M \text{ accepts }x\}$$
Though it can be proved formally that it is neither semi-decidable, nor co-...
- 16.9k
3
votes
Accepted
Infinitely-taped (& "headed"!) Turing Machine: "Stronger" Than Standard
Such a machine can indeed compute every function of type $f : {0,1}* \to \{0,1\}^*$. The gist of the proof is that the transition function has domain $S \times \Sigma^\omega$, where $S$ is the (finite)...
- 3,293
-2
votes
Why, really, is the Halting Problem so important?
I don't think the halting problem has any practical importance. There is a lot of good software to perform termination analysis, and an annual conference on the subject. People claim that the ...
Top 50 recent answers are included