4 ms·

> In computability theory, a system of data-manipulation rules (such as a model of computation, a computer's instruction set, a programming language, or a cellu

> In computability theory, a system of data-manipulation rules (such as a model of computation, a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Turing machine (devised by English mathematician and computer scientist Alan Turing). From https://en.wikipedia.org/wiki/Turing_completeness https://en.wikipedia.org/wiki/Turing_completeness

uxp8u61q 3y ago
... Yes? What are you trying to say? Did you go and lookup what a Turing machine is? Or read the section entitled "Non-mathematical usage"?
- kweingar 3y ago
  You said > It doesn't make sense to say that a bunch of operations are or are not Turing complete. and the article’s first sentence says that a “system of rules” such as a computer’s instruction set can be Turing complete. The article matches my understanding, which is that Turing completeness is a property describing the expressive power of a bunch of operations. You don’t need a computer with infinite memory, or even any physical computer at all, for a bunch of operations to be Turing complete.
Scarblac 3y ago
And Turing machines have unbounded memory. That's usually ignored when talking about Turing completeness, but it's nevertheless true that physical computers cannot simulate all Turing machines.
- Dylan16807 3y ago
  What makes you say a physical computer doesn't have unbounded memory? Is it making assumptions about the real world that we have to make?
- kweingar 3y ago
  > it's nevertheless true that physical computers cannot simulate all Turing machines Right, I wasn’t arguing that physical computers can be Turing machines, but instead that sets of operations can be Turing complete. There are sets of operations with which one can compose a program that perfectly simulates a Turing machine. The problem is that physical computers cannot always run these programs accurately, due to memory constraints. But the set of operations is itself Turing complete.

uxp8u61q 3y ago

... Yes? What are you trying to say? Did you go and lookup what a Turing machine is? Or read the section entitled "Non-mathematical usage"?

kweingar 3y ago
You said > It doesn't make sense to say that a bunch of operations are or are not Turing complete. and the article’s first sentence says that a “system of rules” such as a computer’s instruction set can be Turing complete. The article matches my understanding, which is that Turing completeness is a property describing the expressive power of a bunch of operations. You don’t need a computer with infinite memory, or even any physical computer at all, for a bunch of operations to be Turing complete.

Scarblac 3y ago

And Turing machines have unbounded memory. That's usually ignored when talking about Turing completeness, but it's nevertheless true that physical computers cannot simulate all Turing machines.

Dylan16807 3y ago
What makes you say a physical computer doesn't have unbounded memory? Is it making assumptions about the real world that we have to make?
kweingar 3y ago
> it's nevertheless true that physical computers cannot simulate all Turing machines Right, I wasn’t arguing that physical computers can be Turing machines, but instead that sets of operations can be Turing complete. There are sets of operations with which one can compose a program that perfectly simulates a Turing machine. The problem is that physical computers cannot always run these programs accurately, due to memory constraints. But the set of operations is itself Turing complete.