3 ms·

Isn't there some kind of universality principle where anything that is complicated enough is Turing complete if you let it have infinite memory, and that the su

by ftxbro 3y ago

Isn't there some kind of universality principle where anything that is complicated enough is Turing complete if you let it have infinite memory, and that the surprising thing is when a complicated process isn't Turing complete? I mean, the transformer architecture seems obviously complicated enough to be Turing complete. It's just that it has a finite number of layers and it seems to need a lot of computation to train its weights.

garganzol 3y ago
Turing completeness requires the presence of at least three operations: addition, negation, branching. A usual Neural Network (NN) implements only two operations though: addition and negation. The branching operation can be achieved by: 1) recursion as in Recursive Neural Network (RNN), -or/and- 2) some kind of a conditional intermediary loop that occurs between NN runs.
- drpixie 3y ago
  You might be a little pessimistic about needing 3 operators. Turing's original machines have only decision making and substitution. With that you can emulate anything you want, and go on to higher levels and more and more complexity. Apparently even Conway's Game of Life is Turing complete ... it's horribly obtuse but can be used to build something, which is used to build something, and so on, until eventually you have an automata that could compute anything computable (though rather slowly!)
  - garganzol 3y ago
    I'm neither pessimistic nor optimistic. The formal criteria of Turing completeness are dictated by the math. If a system can implement those or equivalent ops in a disguised form - then it is Turing complete.
- Xen9 3y ago
  Educative comment!
- jmalicki 3y ago
  Softmax in attention is, well, a smoothed max function, so it gets you branching kinda... You're choosing which memory cell to use.
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.
aleks224 3y ago
For a set of primitive operations (such as those in Turing machine), how can you be sure that it spans all possible computations? It sounds that's one of the challenges Turing had - so he went at lengths to show that by various "soft arguments", e.g. that it's possible to build a VM (Turing machine that runs other Turing machines IIRC). Later on, it was shown that the Turing machine is equivalent to machines other folks came up with (Goedel's recursive functions, lambda calculus, etc) and a consensus emerged that they are all describing a full set of computations.

by ftxbro 3y ago

garganzol 3y ago

Turing completeness requires the presence of at least three operations: addition, negation, branching. A usual Neural Network (NN) implements only two operations though: addition and negation. The branching operation can be achieved by: 1) recursion as in Recursive Neural Network (RNN), -or/and- 2) some kind of a conditional intermediary loop that occurs between NN runs.

drpixie 3y ago
You might be a little pessimistic about needing 3 operators. Turing's original machines have only decision making and substitution. With that you can emulate anything you want, and go on to higher levels and more and more complexity. Apparently even Conway's Game of Life is Turing complete ... it's horribly obtuse but can be used to build something, which is used to build something, and so on, until eventually you have an automata that could compute anything computable (though rather slowly!)
- garganzol 3y ago
  I'm neither pessimistic nor optimistic. The formal criteria of Turing completeness are dictated by the math. If a system can implement those or equivalent ops in a disguised form - then it is Turing complete.
Xen9 3y ago
Educative comment!
jmalicki 3y ago
Softmax in attention is, well, a smoothed max function, so it gets you branching kinda... You're choosing which memory cell to use.

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.

aleks224 3y ago

For a set of primitive operations (such as those in Turing machine), how can you be sure that it spans all possible computations? It sounds that's one of the challenges Turing had - so he went at lengths to show that by various "soft arguments", e.g. that it's possible to build a VM (Turing machine that runs other Turing machines IIRC). Later on, it was shown that the Turing machine is equivalent to machines other folks came up with (Goedel's recursive functions, lambda calculus, etc) and a consensus emerged that they are all describing a full set of computations.