3 ms·
The control flow graph section of the README is my favorite part. Is there some thing like the lambda calculus that corresponds to this? I.e., the Turing compl
by ashton314 5y ago
The control flow graph section of the README is my favorite part.
Is there some thing like the lambda calculus that corresponds to this? I.e., the Turing completeness of a single instruction?
- schoen 5y agoThere's apparently a whole field about this: https://en.wikipedia.org/wiki/One-instruction_set_computer https://en.wikipedia.org/wiki/One-instruction_set_computer (I don't know what's known about how to tell whether or not a particular instruction will be Turing complete. Maybe, as in many other parts of computer science, you can do it by reductions: FOO is Turing complete if you can implement BAR with it, where BAR is already known to be Turing complete; BAZ is not Turing complete if you can implement it with QUX, where QUX is already known not to be Turing complete?)