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 ...
- 8,114
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 ...
- 923
Only top scored, non community-wiki answers of a minimum length are eligible