3 ms·
> we prove that flat origami, when viewed as a computational device, is Turing complete, or more specifically P-complete ...aren't those mutually exclusive? I
by NooneAtAll3 2y ago
> we prove that flat origami, when viewed as a computational device, is Turing complete, or more specifically P-complete
...aren't those mutually exclusive?
I feel a mix of "those are obviously different complexity levels" and "is it like C pre-processor turing-completeness situation?"
- lambdaone 2y agoMy understanding of this is that P-completeness for a problem implies that any problem in P can be transformed into it with a polynomial-time reduction. Deterministic Turing machines (more precisely, the problem of determining the future state of a deterministic Turing machine) are in P.
- tromp 2y agoNot with a polynomial-time reduction though. Quoting from [1]: > Generically, reductions stronger than polynomial-time reductions are used, since all languages in P (except the empty language and the language of all strings) are P-complete under polynomial-time reductions. [1] https://en.wikipedia.org/wiki/P-complete https://en.wikipedia.org/wiki/P-complete
- cartoffal 2y agoTuring completeness and P completeness are completely different things. There is no sense in which P-completeness is a "more specific" version of Turing-completeness.