New answers tagged computability
-2
votes
Technical limitations of Turing machines due to the input and output encoding of values
For convenience, I will change the problem conventions slightly: instead of viewing encodings like $\gamma_i$ and $\gamma_o$ as functions from $\mathbb{N}$ to infinite binary strings with finitely ...
1
vote
Accepted
Technical limitations of Turing machines due to the input and output encoding of values
I claim that surjective output encodings $\gamma_{\mathrm{o}}$ are possible, and indeed, every output encoding $\gamma_o$ is allowed as part of a proper encoding.
First, I claim that we we can arrange ...
- 185
-1
votes
Computational power of probabilistic automata
Your understanding of probabilistic automata (PAs) and their role in the theory of computation is quite insightful. Probabilistic automata indeed introduce a probabilistic element into the computation ...
- 27
Top 50 recent answers are included