2
votes
Complexity of simulations in simulations
You can build a universal Turing machine with only 7 states, or only 15 states if you require that the tape store binary symbols. See https://en.wikipedia.org/wiki/Universal_Turing_machine#...

D.W.♦
- 156k
2
votes
Accepted
Expression with fastest growth in lambda-calculus
Ok, I want to interpret this question as: what is the biggest growth rate a term $t$ of size $|t| = C$ can have, after $n$ $\beta$-reductions (as a function of $n$).
There are several different ...
1
vote
If the Navier-Stokes equations problem is a computable problem, for example a set/language called "L", what are the elements of L?
Languages are a good way of discussing yes or no questions with a finite bit-length input size. There are plenty of alternatives to languages, in complexity theory! They often have some 'moral ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
computability × 2040turing-machines × 726
undecidability × 407
complexity-theory × 292
reductions × 224
halting-problem × 167
formal-languages × 163
semi-decidability × 128
computation-models × 117
automata × 79
decision-problem × 68
algorithms × 62
context-free × 62
terminology × 62
turing-completeness × 58
finite-automata × 55
primitive-recursion × 54
recursion × 53
regular-languages × 49
proof-techniques × 47
np-complete × 45
logic × 45
formal-grammars × 38
programming-languages × 38
closure-properties × 37