3 ms·
It's worth noting that "just generating text based on probabilities" describe Markov algorithms [1], which are Turing-complete. People overestimate how much it
by vidarh 4y ago
It's worth noting that "just generating text based on probabilities" describe Markov algorithms [1], which are Turing-complete. People overestimate how much it takes to end up with something Turing-complete.[Markov algorithms only generate text with probability 100% or 0% based on whether a certain rule matches or not, so it's even simpler]
(A Markov algorithm is distinct from a Markov chain, but as far as I can tell you could emulate a Markov algorithm with a Markov chain with sufficient number of input states, transitions clamped to 0% or 100%, and allowing it to iterate over its own output; with a large enough state machine, iteration, and a mechanism to provide memory it's almost hard not to end up with a Turing machine)
[1] https://en.wikipedia.org/wiki/Markov_algorithm https://en.wikipedia.org/wiki/Markov_algorithm