Markov, algoritmo di

Markov, algoritmo di

Markov, algoritmo di sistema di riscrittura di stringhe costruito sulla base di una lista di regole. Gli algoritmi di Markov possono rappresentare ogni espressione matematica calcolabile e sono quindi un modello generale di calcolo (si usa dire che è un sistema Turing completo, nel senso che ogni funzione Turing-calcolabile è rappresentabile in questo simbolismo). Essi sono costituiti da un insieme di regole di riscrittura della forma

e da alcune regole di terminazione.

Data una stringa come input, si cerca nell’elenco delle regole, in ordine a partire dalla prima, quella che contiene come pattern una parte dell’input dato. Se essa non viene trovata l’algoritmo termina, altrimenti viene rimpiazzato il pattern trovato più a sinistra nella stringa e la procedura continua. Per esempio, il sistema di regole che segue riscrive un numero naturale n scritto in forma binaria come una sequenza di n barrette verticali.

Regole:

a) | 0 → 0 ||

b) 1 → 0 |

c) 0 →

L’ultima è una regola di terminazione che al simbolo 0 sostituisce il carattere vuoto (qui indicato come assenza di caratteri).

Input:

110 (rappresenta nel sistema binario il numero sei)

Esecuzione (l’applicazione di una delle regole da una stringa a un’altra è indicata con ⇒):