News for hackers. Stuff that matters.

A comment on Accidentally Turing-Complete. Parent comment

Re:Accidentally Turing-Complete by Dylan16807 on Friday April 24, 2020 @03:15PM (#22971851)
When people talk about "limited time and/or memory" for a runtime they're almost certainly talking about something constant, or a small polynomial of the input size.

But yes, it should reduce to NP territory. If you actually had a nondeterministic CPU, then for most use cases you could fully evaluate these machines in seconds.

[ Parent | on HN ]
Re:Accidentally Turing-Complete by a1369209993 on Friday April 24, 2020 @04:33PM (#22972627)
> limited time [to] a small polynomial of the input size.

This is backwards; I meant that if you have any time bound whatsoever, the number of inputs you can inspect is limited to (a architecture-specific finite multiple of) the number of operations you can execute (because inspecting a input is such a operation).

[ Parent | on HN ]
Re:Accidentally Turing-Complete by Dylan16807 on Friday April 24, 2020 @05:39PM (#22973200)
I wasn't talking about your argument that the calculation is finite. I was talking about how N is chosen in the first place.
[ Parent | on HN ]