3 ms·
No, because being in NP restricts computations to a polynomial number of (non-deterministic) steps.
by tromp 4y ago
No, because being in NP restricts computations to a polynomial number of (non-deterministic) steps.
- joe_the_user 4y agoWell, myself and the gp were referring to the approach of the OP, saying "X is Turing complete" meaning "would be Turing complete if you add these extra elements, like a tape or whatever". If you start with a time-limited Turing Machine and remove the time-limit, then you have a full Turing Machine now don't you. Don't take any of this very seriously, my comment was more about the looseness of the whole approach in the article than any significant claim.