Markov algoritm

Inom teoretisk datavetenskap är en Markov-algoritm ett strängomskrivningssystem som använder grammatikliknande regler för att arbeta på strängar av symboler. Markov-algoritmer har visat sig vara Turing-kompletta , vilket betyder att de är lämpliga som en allmän beräkningsmodell och kan representera vilket matematiskt uttryck som helst utifrån dess enkla notation. Markovs algoritmer är uppkallade efter den sovjetiske matematikern Andrey Markov, Jr.

Refal är ett programmeringsspråk baserat på Markov-algoritmer.

Beskrivning

Normala algoritmer är verbala, det vill säga avsedda att användas på strängar i olika alfabet.

Definitionen av en normal algoritm består av två delar: definitionen av algoritmens alfabet (algoritmen kommer att tillämpas på strängar av dessa alfabetssymboler) och definitionen av dess schema . Schemat för en normal algoritm är en ändligt ordnad uppsättning så kallade substitutionsformler , som var och en kan vara enkel eller slutgiltig . Enkla substitutionsformler representeras av strängar av formen $L\to D$ , där $L$ och $D$ är två godtyckliga strängar i alfabetet för algoritmen (kallas resp. , vänster och höger sida av formelsubstitutionen). På liknande sätt representeras slutliga substitutionsformler av strängar av formen $L\to \cdot D$ , där $L$ och $D$ är två godtyckliga strängar i alfabetet i algoritm. Detta förutsätter att hjälptecknen $\to$ och $\to \cdot$ inte tillhör alfabetet för algoritmen (annars två andra tecken för att utföra sin roll som avdelare mellan vänster och höger sidor, som inte finns i algoritmens alfabet, bör väljas).

Här är ett exempel på ett normalt algoritmschema i alfabetet med fem bokstäver $|*abc$ :

\left\{{\begin{matrix}|b&\to &ba|\\ab&\to &ba\\b&\to &\\{*}|&\to &b*&\\{* }&\to &c&\\|c&\to &c\\ac&\to &c|\\c&\to \cdot \end{matris}}\right.

Processen att tillämpa den normala algoritmen på en godtycklig sträng $V$ i alfabetet för denna algoritm är en diskret sekvens av elementära steg, bestående av följande. Låt oss anta att $V'$ är ordet som erhölls i föregående steg i algoritmen (eller det ursprungliga ordet ${\displaystyle V} ,$ om det aktuella steget är det första). Om av substitutionsformlerna det inte finns någon vänstra sida som ingår i ${\displaystyle V'},$ avslutas algoritmen, och resultatet av dess arbete anses vara strängen $V'$ . Annars väljs den första av substitutionsformlerna vars vänstra sida ingår i ${\displaystyle V'} .$ Om substitutionsformeln har formen $L\to \cdot D$ , då av alla möjliga representationer av strängen $V'$ av formen $RLS$ (där $R$ och ${\displaystyle S} är godtyckliga strängar)$ väljs den med kortast ${\displaystyle R} .$ Sedan avslutas algoritmen och resultatet av dess arbete anses vara $RDS$ . Men om denna ersättningsformel har formen $L\to D$ , då av alla möjliga representationer av strängen $V'$ av formen ${\ displaystyle RLS} väljs$ den med kortast $R$ , varefter strängen $RDS$ anses vara resultatet av det aktuella steget, med förbehåll för vidare bearbetning i nästa steg.

Till exempel, processen att tillämpa algoritmen som beskrivs ovan på ordet $|*||$ resulterar i ordföljden $|b*|$ , $ba|*|$ , $a|*|$ , $a|b*$ , $aba|*$ , $baa|*$ , $aa|*$ , $aa|c$ , $aac$ , $ac|$ och $c||$ , varefter algoritmen slutar med resultatet $||$ .

För andra exempel, se nedan.

Vilken normal algoritm som helst motsvarar någon Turing-maskin och vice versa – vilken Turing-maskin som helst är likvärdig med någon normal algoritm. En version av Church-Turing-avhandlingen formulerad i relation till den normala algoritmen kallas "normaliseringsprincipen".

Normala algoritmer har visat sig vara ett bekvämt sätt att bygga många delar av konstruktiv matematik . Dessutom, inneboende i definitionen av en normal algoritm finns ett antal idéer som används i programmeringsspråk som syftar till att hantera symbolisk information – till exempel i Refal .

Algoritm

Reglerna är en sekvens av par av strängar, vanligtvis presenterade i form av mönster → ersättning . Varje regel kan vara antingen vanlig eller avslutande.

Givet en inmatningssträng :

Kontrollera reglerna i ordning uppifrån och ned för att se om något av mönstren kan hittas i inmatningssträngen .
Om ingen hittas stoppas algoritmen.
Om en (eller flera) hittas, använd den första av dem för att ersätta förekomsten längst till vänster av matchad text i inmatningssträngen med dess ersättning .
Om den nyss tillämpade regeln var en avslutande, stannar algoritmen.
Gå till steg 1.

Observera att efter varje regeltillämpning börjar sökningen om från den första regeln.

Exempel

Följande exempel visar den grundläggande operationen för en Markov-algoritm.

Regler

"A" -> "äpple"
"B" -> "väska"
"S" -> "butik"
"T" -> "den"
"butiken" -> "min bror"
"en aldrig använd" -> . "avslutande regel"

Symbol sträng

"Jag köpte en B av As från TS."

Avrättning

Om algoritmen tillämpas på exemplet ovan kommer symbolsträngen att ändras på följande sätt.

"Jag köpte en B av As från TS."
"Jag köpte en B av äpplen från T S."
"Jag köpte en påse äpplen från T S."
"Jag köpte en påse äpplen från T shop."
"Jag köpte en påse äpplen från butiken."
"Jag köpte en påse äpplen av min bror."

Algoritmen kommer då att avslutas.

Ett annat exempel

Dessa regler ger ett mer intressant exempel. De skriver om binära tal till sina unära motsvarigheter. Till exempel kommer 101 att skrivas om till en sträng med 5 på varandra följande staplar.

Regler

"|0" -> "0||"
"1" -> "0|"
"0" -> ""

Symbol sträng

"101"

Avrättning

Om algoritmen tillämpas på exemplet ovan kommer den att avslutas efter följande steg.

"101"
"0|01"
"00||1"
"00||0|"
"00|0|||"
"000|||||"
"00|||||"
"0|||||"
"|||||"

Se även

Caracciolo di Forino, A. Strängbearbetningsspråk och generaliserade Markov-algoritmer. I Symbol manipulation languages and techniques, GD Bobrow (Ed.), North-Holland Publ. Co., Amsterdam, Nederländerna, 1968, s. 191–206.
Andrey Andreevich Markov (1903-1979) 1960. The Theory of Algoritms. American Mathematical Society Translations, serie 2, 15, 1-14. (Översättning från ryska, Trudy Instituta im. Steklova 38 (1951) 176-189)

^ Kushner, Boris A. (1999-05-28). "Markovs konstruktiva analys; en deltagares syn" . Teoretisk datavetenskap . 219 (1–2): 268, 284. doi : 10.1016/S0304-3975(98)00291-6 .

externa länkar

[1] Kushner, Boris A. (1999-05-28). "Markovs konstruktiva analys; en deltagares syn" . Teoretisk datavetenskap . 219 (1–2): 268, 284. doi : 10.1016/S0304-3975(98)00291-6 .