3 ms·
Well yeah, With this loose definition of Turing complete - manipulations of a thing with a finite number of states that could be infinite by extension (you sup
by joe_the_user 4y ago
Well yeah,
With this loose definition of Turing complete - manipulations of a thing with a finite number of states that could be infinite by extension (you supply the manipulations) - then everything that's NP-complete is Turing complete, including Microsoft's Minesweeper and clones.
- tromp 4y agoNo, 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.