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 ...
-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 ...
Top 50 recent answers are included
Related Tags
computability × 397turing-machines × 88
cc.complexity-theory × 69
reference-request × 55
lo.logic × 51
pl.programming-languages × 34
automata-theory × 26
decidability × 24
fl.formal-languages × 22
complexity-classes × 18
lambda-calculus × 18
universal-computation × 17
halting-problem × 17
machine-models × 15
randomness × 13
undecidability × 13
soft-question × 11
time-complexity × 10
kolmogorov-complexity × 10
computing-over-reals × 10
cellular-automata × 10
ds.algorithms × 9
oracles × 9
computable-analysis × 9
type-theory × 8