News for hackers. Stuff that matters.

A comment on Turing Oversold?. Parent comment

Re:Turing Oversold? by Ar-Curunir on Thursday September 16, 2021 @12:41PM (#28554001)
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.

[ Parent | on HN ]
Re:Turing Oversold? by SquishyPanda23 on Thursday September 16, 2021 @03:09PM (#28555905)
> Mechanical computers approximate Turing Machines

Yup, so do humans with paper and pencil.

[ Parent | on HN ]