Algoritmo de Markov
Em teoria da computação, o algoritmo de Markov, nomeado assim em homenagem à Andrei Markov, é um sistema de reescrita de cadeias que lança mão de regras de gramáticas para operar sobre cadeias de símbolos. Os algoritmos de Markov se mostraram Turing-completos, o que garante que eles provêm um modelo geral de computação e que podem representar qualquer expressão matemática.[carece de fontes?]
Imagem: Mmarpe · BY-SA · Openverse
As Regras constituem-se de uma sequência de pares de cadeias, usualmente presentes na forma padrão->substituição. Algumas regras podem ser conclusivas.
Os seguintes exemplos mostram o operacional básico de um algoritmo de Markov.
Primeiro exemplo
Quando o algoritmo for aplicado sobre o exemplo acima, ele mostrará esta sequência de configurações: Parando devido à falta de padrões encontrados.[carece de fontes?]
Segundo exemplo
Estas regras mostram um caso mais interessante. Elas transformam números binários em suas representações unárias. Neste exemplo, o número 101 será reescrito como 5 barras consecutivas.[carece de fontes?] Quando o algoritmo for aplicado sobre o exemplo acima, ele mostrará esta sequência de configurações: Novamente parando devido à falta de padrões encontrados.
