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.'s user avatar
  • 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 ...
cody's user avatar
  • 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 ...
Alex Meiburg's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible