News for hackers. Stuff that matters.

A comment on How to Build an Origami Computer.

Re:How to Build an Origami Computer by jksk61 on Tuesday January 30, 2024 @04:37PM (#39196216)
now the question is: what is the most complex* object that it is not turing complete?

* let's say you have n distinct rules acting against a set S, the complexity is n.

p.s. probably something trivial exists such that you can take n as large as we wish to, so probably my definitions are not interesting.

[ Parent | on HN ]
Re:How to Build an Origami Computer by andrewflnr on Tuesday January 30, 2024 @07:07PM (#39197865)
I think complexity is entirely the wrong question to ask regarding Turing completeness. It's about the kind of rules, not how many.

That said, maybe the cheekiest answer is an actual computer: fantastically complex, but technically TC requires infinite memory.

[ Parent | on HN ]
Re:How to Build an Origami Computer by charcircuit on Tuesday January 30, 2024 @07:27PM (#39198039)
Come up with something complex and give it finite memory.
[ Parent | on HN ]