3 ms·
Mechanical computers approximate Turing Machines, just like NP approximates RE: instead of asking “does this program halt?”, we ask “does this program halt in N
by Ar-Curunir 5y ago
Mechanical computers approximate Turing Machines, just like NP approximates RE: instead of asking “does this program halt?”, we ask “does this program halt in N steps?”.
If N is sufficiently (polynomially) large, the two are approximately equal.
- SquishyPanda23 5y ago> Mechanical computers approximate Turing Machines Yup, so do humans with paper and pencil.