4 ms·

Great point My personal theory is that anything you can run on a computer is Turing complete Essentially any algorithm needs an interpreter that runs it So i

by nico 3y ago

Great point My personal theory is that anything you can run on a computer is Turing complete Essentially any algorithm needs an interpreter that runs it So if your algorithm runs on a computer, then in includes the whole computer Like if you are truly statically linking code, it should include the whole computer with it And that system is most definitely Turing complete So probably when a complex enough algorithm runs on a computer, it might be big enough that you need a significant part of the abstractions of the computer system itself to explain the behavior of the algorithm, so the algorithm ends up including the requirements for Turing completeness

ftxbro 3y ago
OK but I understand that systems like finite state machines and parenthesis matchers aren't Turing complete.
godelski 3y ago
This is definitely not true. There are context-free grammar and finite state machines are not Turing complete (TC). Strong functional programming languages (always terminate and every action is defined: e.g. x/0=0) are not TC since they exclude the ability to not terminate. In fact, most things you run on a computer are not TC as they are deterministically terminating. Computers themselves are not TC! They have finite memory. For practical purposes they are, and the languages they use often are, but I'd be a bit careful with your "personal theory" as it doesn't capture the ideas of TC that well.
- kaba0 3y ago
  We really should not be boggled down by memory of computers. What exactly is its memory? If I have an old machine with a few kb of memory that can connect to the clouds petabytes of storage, how long is my “tape”? What if it is wired to operate a drone and can move real world objects? It’s state space is essentially the universe (which is finite, so yeah, theoretically not even that is infinite).
Lornedon 3y ago
That's like saying that everything you build with Lego is a pirate ship: To build anything with Lego, you first need Lego bricks. And if you already have those, then you can also build a pirate ship. Turing completeness is defined on computational models, i.e. sets of instructions that you can use to build algorihms. Not on the algorithms themselves. If you can simulate a Turing machine using only the tools that your model gives you, then it's Turing complete. That doesn't mean that everything else you build using those tools is special in any way.
- nico 3y ago
  You don’t need a pirate ship to build legos But you do need an interpreter to interpret/run any algorithm So you can never really separate the algorithm from the interpreter for any practical application If your algorithm requires the capabilities that define an interpreter as Turing-complete, then the algorithm will be Turing complete as well
  - ftxbro 3y ago
    is this a derridean 'il n'y a pas de hors-texte' deconstruction of the chomsky hierarchy because if it is then i'm here for it
    - nico 3y ago
      Had never heard of the concept of ‘lil n’y a pas de hors-texted’, reading about it sounds like the same concept: can’t remove the context from the object > Understood as such, it's not really such a strange idea, that the things outside of the text itself can and do give meaning to it in an ever-evolving way. In a philosophical context we can understand it to assert the idea that context is always present, and isn't necessarily stable. From: https://philosophy.stackexchange.com/a/40227 https://philosophy.stackexchange.com/a/40227

by nico 3y ago

ftxbro 3y ago

OK but I understand that systems like finite state machines and parenthesis matchers aren't Turing complete.

godelski 3y ago

This is definitely not true. There are context-free grammar and finite state machines are not Turing complete (TC). Strong functional programming languages (always terminate and every action is defined: e.g. x/0=0) are not TC since they exclude the ability to not terminate. In fact, most things you run on a computer are not TC as they are deterministically terminating. Computers themselves are not TC! They have finite memory. For practical purposes they are, and the languages they use often are, but I'd be a bit careful with your "personal theory" as it doesn't capture the ideas of TC that well.

kaba0 3y ago
We really should not be boggled down by memory of computers. What exactly is its memory? If I have an old machine with a few kb of memory that can connect to the clouds petabytes of storage, how long is my “tape”? What if it is wired to operate a drone and can move real world objects? It’s state space is essentially the universe (which is finite, so yeah, theoretically not even that is infinite).

Lornedon 3y ago

That's like saying that everything you build with Lego is a pirate ship: To build anything with Lego, you first need Lego bricks. And if you already have those, then you can also build a pirate ship. Turing completeness is defined on computational models, i.e. sets of instructions that you can use to build algorihms. Not on the algorithms themselves. If you can simulate a Turing machine using only the tools that your model gives you, then it's Turing complete. That doesn't mean that everything else you build using those tools is special in any way.

nico 3y ago
You don’t need a pirate ship to build legos But you do need an interpreter to interpret/run any algorithm So you can never really separate the algorithm from the interpreter for any practical application If your algorithm requires the capabilities that define an interpreter as Turing-complete, then the algorithm will be Turing complete as well
- ftxbro 3y ago
  is this a derridean 'il n'y a pas de hors-texte' deconstruction of the chomsky hierarchy because if it is then i'm here for it
  - nico 3y ago
    Had never heard of the concept of ‘lil n’y a pas de hors-texted’, reading about it sounds like the same concept: can’t remove the context from the object > Understood as such, it's not really such a strange idea, that the things outside of the text itself can and do give meaning to it in an ever-evolving way. In a philosophical context we can understand it to assert the idea that context is always present, and isn't necessarily stable. From: https://philosophy.stackexchange.com/a/40227 https://philosophy.stackexchange.com/a/40227