5 ms·

Interesting, I thought it was proven Transformers cannot do recursion[0] and aren't actually able to be equivalent to a turing machine due to lack of expandable

by f_devd 2y ago

Interesting, I thought it was proven Transformers cannot do recursion[0] and aren't actually able to be equivalent to a turing machine due to lack of expandable memory, and are rather finite state automata. [0]: https://youtu.be/rie-9AEhYdY?si=5p0QCxAFovGUHFRb&t=1744 https://youtu.be/rie-9AEhYdY?si=5p0QCxAFovGUHFRb&t=1744

golol 2y ago
People always makes these points of things not being technically Turing machines because they are finite, they have finite memory. Well, obviously! Your computer has finite memory too. It doesn't matter in practice, and the conceptual idea that this thing can do arbitrary computations is more important.
- f_devd 2y ago
  The argument isn't finite memory but rather the lack of it being expandable memory; as in it cannot learn to read/write to a hypothetical infinite tape. (Although I'm maybe not the right person to word it, I recommend the prior linked video)
  - golol 2y ago
    The nature of computation is just not about extendability of memory for me. It's just a technicality.
  - fl7305 2y ago
    > it cannot learn to read/write to a hypothetical infinite tape Modern LLMs can perform external function calling. How is that not the same as having access to a potentially infinite memory? Conversely, your brain does not contain infinite storage. So it is clearly not Turing complete in the strictest sense. Does that tell us anything useful about the level of intelligence in a brain?
    - f_devd 2y ago
      > Conversely, your brain does not contain infinite storage. But you can address it and use it, you can think of a system which can make use of infinite memory and then execute that system. LLMs they cannot use something like `set(0x8080, "ABC")` and later retrieve that with `get(0x8080)` without keeping the initial command in it's context therefore it's memory is not expandable. Likewise LLMs can call a external function but the input of the LLM is a fixed context on which it's trained, and it has a fixed amount of time to use that context so it's not expandable. Now this is not necessarily a limitation of the architecture, but rather how we train NNs. It's also not a necessity to do something useful but the efficient/optimal solution for many problems are often turing-complete and are thus not findable or even searchable by NNs. The video goes into more depth everything metioned, and on the distinction between turing machines and NN limitations.
      - drdeca 2y ago
        A finite state machine can control the head of a Turing machine (as, that is what controls the head of a Turing machine). A transformer could be trained to implement a particular finite state machine (using a fixed length context window). Of course, so could a fully connected 1-hidden-layer feed-forward neural network. Though, a lookup table would probably be more practical than either of those. I'm not saying much here, just that "technically, a transformer equipped with interaction with another system, can be Turing complete (though not necessarily in a way that matters)." . Giving a finite state machine the ability to read and write finite amounts of information to memory addresses (where each address can only store a finite amount of info), only goes beyond being a (perhaps much larger) finite state machine, if there are infinitely many memory locations that can be used, and so these locations can't be limited to ones that have an address which can be specified entirely in terms of a state of the finite state machine. the following is a tangent: Sometimes I wonder about, "If we wanted to design a computer that used silicon chips and other such electrical components, but was modular in a way that would make it technically Turing complete as long as we connected (and provided adequate power to) additional modules whenever it tried to use the next one it is missing, what would be a good way to design that?". A single tape of symbols, or even several tapes, where it can only move one position at a time (per tape), seems probably inefficient (though perhaps not in any asymptotic sense). But, if one can only jump to positions labeled by addresses of a bounded length, that's no good. Therefore, I think that maybe a good solution would be to use relative addresses, where the offsets have a maximum size of 2^32 or 2^16 or something. I think that, in order to prevent computation at later memory addresses from being slower, having to send the information back and forth between the module where it is stored and the information describing the FSM/program, it might be good to have either all the modules, or some fraction of them, contain copies of the hardware for running the computation steps, not just forwarding and implementing messages to read/write. Though, in that case, it does seem a bit of a waste to not use parallelism. Alternatively, I suppose having a literally-moving head, which stores the FSM, and moves between the different memory modules, might make sense?
trashtester 2y ago
I'm pretty sure any physically realizable computer is a Finite State Machine (FSM). The Turing Machine assumptions of infinite memory and unbounded time lead to a lot of poor intuitions about them, in my experience. That bad intuitions would also apply to FSM's, though. Or to the human brain for that matter. For instance, a well trained human brain may be Turing Complete, if they can access some external storage (like pen&paper). This leads to confused concepts such as the Chinese Room argument. Even though a human brain can contain a Turing Machine, it doesn't mean that understanding a Turing Machine gives much relevant understanding of how the Brain normally operates. The native compute model of the brain is completely different.
- nyrikki 2y ago
  LLMs are pessimisticly constrained to being equivalent to TC0 or more specifically are uniform consent depth threshold circuits. Circuits and TMs are very different, but while LLMs can use threshold circuits, they do not have access to finite size input parity circuits, nor can they do operations like xor in a single layer. It is the cost of high parallelism. For those who are trying to figure out real world applications, it is worth the effort to learn circuit complexity, as it will be far more realistic than TM. https://complexityzoo.net/Complexity_Zoo:T#tc0 https://complexityzoo.net/Complexity_Zoo:T#tc0
thomashop 2y ago
Isn't recursion solved by just feeding the output of the LLM (with some additional instructions) back into the input? That's how a lot of complex problems are already tackled with LLMs.
- westurner 2y ago
  Perhaps similarly, neural activation patterns in biological neural networks are cyclic: there are cycles in the graph (which has oscillating voltage due to the heart being an electrical generator in addition to a pump).

by f_devd 2y ago

golol 2y ago

People always makes these points of things not being technically Turing machines because they are finite, they have finite memory. Well, obviously! Your computer has finite memory too. It doesn't matter in practice, and the conceptual idea that this thing can do arbitrary computations is more important.

f_devd 2y ago
The argument isn't finite memory but rather the lack of it being expandable memory; as in it cannot learn to read/write to a hypothetical infinite tape. (Although I'm maybe not the right person to word it, I recommend the prior linked video)
- golol 2y ago
  The nature of computation is just not about extendability of memory for me. It's just a technicality.
- fl7305 2y ago
  > it cannot learn to read/write to a hypothetical infinite tape Modern LLMs can perform external function calling. How is that not the same as having access to a potentially infinite memory? Conversely, your brain does not contain infinite storage. So it is clearly not Turing complete in the strictest sense. Does that tell us anything useful about the level of intelligence in a brain?
  - f_devd 2y ago
    > Conversely, your brain does not contain infinite storage. But you can address it and use it, you can think of a system which can make use of infinite memory and then execute that system. LLMs they cannot use something like `set(0x8080, "ABC")` and later retrieve that with `get(0x8080)` without keeping the initial command in it's context therefore it's memory is not expandable. Likewise LLMs can call a external function but the input of the LLM is a fixed context on which it's trained, and it has a fixed amount of time to use that context so it's not expandable. Now this is not necessarily a limitation of the architecture, but rather how we train NNs. It's also not a necessity to do something useful but the efficient/optimal solution for many problems are often turing-complete and are thus not findable or even searchable by NNs. The video goes into more depth everything metioned, and on the distinction between turing machines and NN limitations.
    - drdeca 2y ago
      A finite state machine can control the head of a Turing machine (as, that is what controls the head of a Turing machine). A transformer could be trained to implement a particular finite state machine (using a fixed length context window). Of course, so could a fully connected 1-hidden-layer feed-forward neural network. Though, a lookup table would probably be more practical than either of those. I'm not saying much here, just that "technically, a transformer equipped with interaction with another system, can be Turing complete (though not necessarily in a way that matters)." . Giving a finite state machine the ability to read and write finite amounts of information to memory addresses (where each address can only store a finite amount of info), only goes beyond being a (perhaps much larger) finite state machine, if there are infinitely many memory locations that can be used, and so these locations can't be limited to ones that have an address which can be specified entirely in terms of a state of the finite state machine. the following is a tangent: Sometimes I wonder about, "If we wanted to design a computer that used silicon chips and other such electrical components, but was modular in a way that would make it technically Turing complete as long as we connected (and provided adequate power to) additional modules whenever it tried to use the next one it is missing, what would be a good way to design that?". A single tape of symbols, or even several tapes, where it can only move one position at a time (per tape), seems probably inefficient (though perhaps not in any asymptotic sense). But, if one can only jump to positions labeled by addresses of a bounded length, that's no good. Therefore, I think that maybe a good solution would be to use relative addresses, where the offsets have a maximum size of 2^32 or 2^16 or something. I think that, in order to prevent computation at later memory addresses from being slower, having to send the information back and forth between the module where it is stored and the information describing the FSM/program, it might be good to have either all the modules, or some fraction of them, contain copies of the hardware for running the computation steps, not just forwarding and implementing messages to read/write. Though, in that case, it does seem a bit of a waste to not use parallelism. Alternatively, I suppose having a literally-moving head, which stores the FSM, and moves between the different memory modules, might make sense?

trashtester 2y ago

I'm pretty sure any physically realizable computer is a Finite State Machine (FSM). The Turing Machine assumptions of infinite memory and unbounded time lead to a lot of poor intuitions about them, in my experience. That bad intuitions would also apply to FSM's, though. Or to the human brain for that matter. For instance, a well trained human brain may be Turing Complete, if they can access some external storage (like pen&paper). This leads to confused concepts such as the Chinese Room argument. Even though a human brain can contain a Turing Machine, it doesn't mean that understanding a Turing Machine gives much relevant understanding of how the Brain normally operates. The native compute model of the brain is completely different.

nyrikki 2y ago
LLMs are pessimisticly constrained to being equivalent to TC0 or more specifically are uniform consent depth threshold circuits. Circuits and TMs are very different, but while LLMs can use threshold circuits, they do not have access to finite size input parity circuits, nor can they do operations like xor in a single layer. It is the cost of high parallelism. For those who are trying to figure out real world applications, it is worth the effort to learn circuit complexity, as it will be far more realistic than TM. https://complexityzoo.net/Complexity_Zoo:T#tc0 https://complexityzoo.net/Complexity_Zoo:T#tc0

thomashop 2y ago

Isn't recursion solved by just feeding the output of the LLM (with some additional instructions) back into the input? That's how a lot of complex problems are already tackled with LLMs.

westurner 2y ago
Perhaps similarly, neural activation patterns in biological neural networks are cyclic: there are cycles in the graph (which has oscillating voltage due to the heart being an electrical generator in addition to a pump).