New answers tagged

-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 ...
user70521's user avatar
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 ...
JDH's user avatar
  • 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 ...
Alfonso F R's user avatar

Top 50 recent answers are included