News for hackers. Stuff that matters.
Re:Attention is Turing complete [pdf] by ftxbro on Wednesday June 14, 2023 @04:59PM (#36332553)
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.
Re:Attention is Turing complete [pdf] by garganzol on Wednesday June 14, 2023 @05:34PM (#36333063)
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.
Re:Attention is Turing complete [pdf] by Xen9 on Wednesday June 14, 2023 @06:40PM (#36333829)
Educative comment!
Re:Attention is Turing complete [pdf] by jmalicki on Thursday June 15, 2023 @01:49AM (#36336877)
Softmax in attention is, well, a smoothed max function, so it gets you branching kinda... You're choosing which memory cell to use.
Re:Attention is Turing complete [pdf] by drpixie on Thursday June 15, 2023 @07:51AM (#36339137)
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!)

Re:Attention is Turing complete [pdf] by garganzol on Thursday June 15, 2023 @08:50AM (#36339721)
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.
Re:Attention is Turing complete [pdf] by nico on Wednesday June 14, 2023 @06:13PM (#36333517)
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

Re:Attention is Turing complete [pdf] by ftxbro on Wednesday June 14, 2023 @06:17PM (#36333554)
OK but I understand that systems like finite state machines and parenthesis matchers aren't Turing complete.
Re:Attention is Turing complete [pdf] by godelski on Wednesday June 14, 2023 @06:58PM (#36334036)
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.
Re:Attention is Turing complete [pdf] by kaba0 on Thursday June 15, 2023 @06:23AM (#36338497)
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).
Re:Attention is Turing complete [pdf] by Lornedon on Wednesday June 14, 2023 @07:22PM (#36334262)
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.

Re:Attention is Turing complete [pdf] by nico on Wednesday June 14, 2023 @11:09PM (#36335968)
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

Re:Attention is Turing complete [pdf] by ftxbro on Wednesday June 14, 2023 @11:30PM (#36336060)
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
Re:Attention is Turing complete [pdf] by nico on Saturday June 17, 2023 @07:12PM (#36375685)
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

Re:Attention is Turing complete [pdf] by aleks224 on Wednesday June 14, 2023 @07:51PM (#36334541)
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.