Attention is Turing complete [pdf]

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.

[ Parent | on HN ]

Re:Attention is Turing complete [pdf] by Xen9 on Wednesday June 14, 2023 @06:40PM (#36333829)

Educative comment!

[ Parent | on HN ]

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.

[ Parent | on HN ]

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!)

[ Parent | on HN ]

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.

[ Parent | on HN ]