2 ms·

Turing completeness is about simulating a Turing machine, not being one.

by ModernMech 4y ago

whimsicalism 4y ago
Nah they're technically correct. You can't simulate a Turing machine with finite memory.
- ModernMech 4y ago
  To simulate something is not to be something. Simulations are approximations of the thing. What you're implying is that we can't simulate anything, as the simulation can never be the thing. Can we not simulate the weather or the solar system because we can't take into account every possible detail? If your position is that nothing can be Turing complete, than why should anyone care about Turing completeness?
  - whimsicalism 4y ago
    We can simulate a model of the weather. We can simulate (as in completely replicate the software behavior of) a gameboy advanced. Not going to keep replying as this is not really a point I am going to get convinced of - to be technically turing complete is to show that every thing computable by a turing machine is computable by your construct. This is not possible in a memory constrained system.
    - ModernMech 4y ago
      Appreciate you've bowed out of this discussion, but what you're saying makes no sense to me, because then we would just say things are or are not Turing machines. The reason we have the term "Turing complete" and not just "Turing machine" is precisely the fact that nothing can literally be a Turing machine, and we need a useful term in discussions of computability nonetheless. The analysis as to whether or not a system is Turing complete or not is done with respect to the operations it can perform, not its memory capacity, or even the time over which is performs the operations, both of which are always assumed to be "enough" rather than infinite.
      - asddubs 4y ago
        >The reason we have the term "Turing complete" and not just "Turing machine" is precisely the fact that nothing can literally be a Turing machine, and we need a useful term in discussions of computability nonetheless. a turing machine is something way more specific than just "something that can execute algorithms" though, it's a machine that executes them using a specific system and constraints (namely advancing and modifying a strip of tape). So calling anything that can compute what a turing machine can compute a turing machine would be inaccurate just by merit of that. of course ultimately you're right though, words mean what they're used to mean, so turing completeness excludes the infinite memory constraint, my initial comment wasn't really meant fully seriously, just being a smartass for a joke.
jasamer 4y ago
Touring completeness is about accurately simulating any Turing machine. Not approximately simulating one (what would that even mean?), or simulating just some of them. When we say something is Turing complete, there’s always an implicit “if it ran on a computer with unlimited memory” assumption that comes with it, because no computer with limited memory can ever simulate all Turing machines. You can always construct a Touring machine that makes a given computer run out of memory. So technically, no real computer or computer program is Turing complete, or able to accurately simulate any Turing machine. The whole thing is an irrelevant technicality though, as A) we have so much memory available that we might as well treat it as unlimited and B) touring completeness is a theoretical property - if you prove it for something like python type hints, that proof won’t assume any memory limitations, ie. it’ll assume the computer the thing runs on has infinite memory. The proof is valid even though no such infinite computer actually exists.

Turing completeness is about simulating a Turing machine, not being one.

whimsicalism 4y ago

Nah they're technically correct. You can't simulate a Turing machine with finite memory.

ModernMech 4y ago
To simulate something is not to be something. Simulations are approximations of the thing. What you're implying is that we can't simulate anything, as the simulation can never be the thing. Can we not simulate the weather or the solar system because we can't take into account every possible detail? If your position is that nothing can be Turing complete, than why should anyone care about Turing completeness?
- whimsicalism 4y ago
  We can simulate a model of the weather. We can simulate (as in completely replicate the software behavior of) a gameboy advanced. Not going to keep replying as this is not really a point I am going to get convinced of - to be technically turing complete is to show that every thing computable by a turing machine is computable by your construct. This is not possible in a memory constrained system.
  - ModernMech 4y ago
    Appreciate you've bowed out of this discussion, but what you're saying makes no sense to me, because then we would just say things are or are not Turing machines. The reason we have the term "Turing complete" and not just "Turing machine" is precisely the fact that nothing can literally be a Turing machine, and we need a useful term in discussions of computability nonetheless. The analysis as to whether or not a system is Turing complete or not is done with respect to the operations it can perform, not its memory capacity, or even the time over which is performs the operations, both of which are always assumed to be "enough" rather than infinite.
    - asddubs 4y ago
      >The reason we have the term "Turing complete" and not just "Turing machine" is precisely the fact that nothing can literally be a Turing machine, and we need a useful term in discussions of computability nonetheless. a turing machine is something way more specific than just "something that can execute algorithms" though, it's a machine that executes them using a specific system and constraints (namely advancing and modifying a strip of tape). So calling anything that can compute what a turing machine can compute a turing machine would be inaccurate just by merit of that. of course ultimately you're right though, words mean what they're used to mean, so turing completeness excludes the infinite memory constraint, my initial comment wasn't really meant fully seriously, just being a smartass for a joke.

jasamer 4y ago

Touring completeness is about accurately simulating any Turing machine. Not approximately simulating one (what would that even mean?), or simulating just some of them. When we say something is Turing complete, there’s always an implicit “if it ran on a computer with unlimited memory” assumption that comes with it, because no computer with limited memory can ever simulate all Turing machines. You can always construct a Touring machine that makes a given computer run out of memory. So technically, no real computer or computer program is Turing complete, or able to accurately simulate any Turing machine. The whole thing is an irrelevant technicality though, as A) we have so much memory available that we might as well treat it as unlimited and B) touring completeness is a theoretical property - if you prove it for something like python type hints, that proof won’t assume any memory limitations, ie. it’ll assume the computer the thing runs on has infinite memory. The proof is valid even though no such infinite computer actually exists.