You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
This is only really true since we usually define an algorithm to be that which is computable by a turing machine or an equivalent model. It makes sense to talk about algorithms that run on turing machines with oracles attached, but these may not be computable by a turing machine alone.
I'd express this more like:
"A Turing machine is a very simple abstract machine designed to capture our intuitive understanding of computation in the most general sense. Any formal system that can simulate a Turing machine, and thus also perform arbitrary computations, is called Turing complete. (Untyped) Lambda calculus is Turing complete."
The text was updated successfully, but these errors were encountered:
Extremely minor quibble re. this footnote:
This is only really true since we usually define an algorithm to be that which is computable by a turing machine or an equivalent model. It makes sense to talk about algorithms that run on turing machines with oracles attached, but these may not be computable by a turing machine alone.
I'd express this more like:
"A Turing machine is a very simple abstract machine designed to capture our intuitive understanding of computation in the most general sense. Any formal system that can simulate a Turing machine, and thus also perform arbitrary computations, is called Turing complete. (Untyped) Lambda calculus is Turing complete."
The text was updated successfully, but these errors were encountered: