Normal algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 november 2021; kontroller kräver 2 redigeringar .

En normal algoritm (algoritm) av Markov ( NAM , även en Markov-algoritm ) är ett av standardsätten att formellt definiera begreppet en algoritm (en annan välkänd metod är en Turing-maskin ). Konceptet med en normal algoritm introducerades av A. A. Markov (junior) i slutet av 1940 -talet i arbeten om olösligheten av vissa problem i teorin om associativa beräkningar. Den traditionella stavningen och uttalet av ordet "algori f m" i denna term går också tillbaka till dess författare, som under många år undervisade i en kurs i matematisk logik vid fakulteten för mekanik och matematik vid Moscow State University .

Den normala algoritmen beskriver en metod för att skriva om strängar, liknande formella grammatiker . NAM är ett Turing-komplett språk, vilket gör det likvärdigt i uttryckskraft med en Turing-maskin och därför med moderna programmeringsspråk. Det funktionella programmeringsspråket Refal skapades på basis av NAM .

Beskrivning

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

Definitionen av en normal algoritm består av två delar: definitionen av algoritmens alfabet (till de ord från vars tecken algoritmen kommer att tillämpas) 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 är ord i formen , där och är två godtyckliga ord i alfabetet för algoritmen (kallas, respektive, vänster och höger sida av substitutionsformeln). På liknande sätt är de slutliga ersättningsformlerna ord i formen , där och är två godtyckliga ord i algoritmens alfabet. Det antas att hjälpbokstäverna och inte tillhör alfabetet i algoritmen (annars bör två andra bokstäver väljas för att spela rollen som en separator mellan vänster och höger del). $L till D$ $L$ $D$ $L\till \cdot D$ $L$ $D$ $\till$ $\till \cdot$

Ett exempel på ett normalt algoritmschema i ett alfabet på fem bokstäver är schemat $|*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å ett godtyckligt ord i alfabetet för denna algoritm är en diskret sekvens av elementära steg, bestående av följande. Låt vara ordet som erhölls vid föregående steg i algoritmen (eller originalordet om det aktuella steget är det första). Om det bland substitutionsformlerna inte finns någon vars vänstra sida skulle inkluderas i , anses algoritmens arbete vara avslutat, och resultatet av detta arbete är ordet . Annars, bland substitutionsformlerna, vars vänstra del ingår i , väljs den allra första. Om denna substitutionsformel har formen , väljs bland alla möjliga representationer av ordet i formen en för vilken är den kortaste, varefter algoritmen anses vara avslutad med resultatet . Om denna ersättningsformel har formen , väljs från alla möjliga representationer av ordet i formen den som är den kortaste, varefter ordet anses vara resultatet av det aktuella steget, med förbehåll för ytterligare bearbetning vid nästa steg. $V$ $V'$ $V$ $V'$ $V'$ $V'$ $L\till \cdot D$ $V'$ $RLS$ $R$ $RDS$ $L till D$ $V'$ $RLS$ $R$ $RDS$

Till exempel, under processen att tillämpa algoritmen med schemat som anges ovan visas orden , , , , , , , , och sekventiellt till ordet , varefter algoritmen avslutas med resultatet . Se fler exempel nedan. $|*||$ $|b*|$ $ba|*|$ $a|*|$ $a|b*$ $aba|*$ $baa|*$ $aa|*$ $aa|c$ $aac$ $ac|$ $c||$ $||$

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 variant av Church-Turing-uppsatsen , formulerad i relation till normala algoritmer, brukar kallas "normaliseringsprincipen".

Normala algoritmer har visat sig vara ett praktiskt verktyg för att konstruera många grenar av konstruktiv matematik . Dessutom används idéerna som är inneboende i definitionen av den normala algoritmen i ett antal programmeringsspråk som är orienterade för bearbetning av symbolisk information - till exempel på språket Refal .

Exempel

Exempel 1

Använder Markov-algoritmen för transformationer på strängar.

Alfabet:

{ a ... i, A ... I, "mellanslag", "punkt" }

Regler:

A → orange
kg till kilogram
M → butik
T → volym
butik →. stall (slutlig formel)
i det båset → på den marknaden

Källrad:

Jag köpte kg Aov i TM.

När algoritmen exekveras genomgår strängen följande ändringar:

Jag köpte ett kg apelsiner på TM.
Jag köpte ett kilo apelsiner på T.M.
Jag köpte ett kilo apelsiner på T-butiken.
Jag köpte ett kilo apelsiner i den butiken.
Jag köpte ett kilo apelsiner i det båset.

Detta slutför exekveringen av algoritmen (eftersom formel nr 5, som vi gjorde slutgiltig, kommer att nås).

Exempel 2

Denna algoritm omvandlar binära tal till " singel " (där posten för ett icke-negativt heltal N är en sträng med N stickor). Till exempel omvandlas det binära talet 101 till 5 pinnar: |||||.

Alfabet:

{ 0, 1, | }

Regler:

1 → 0|
|0 → 0||
0 → "" (tom sträng)

Källrad:

101

Prestanda:

0|01
0|00|
00||0|
00|0|||
000|||||
00|||||
0|||||
|||||

Se även

Andra abstrakta implementerare och formella datorsystem

Språk baserade på normala algoritmer

REVAL
tors

Andra algoritmer

Operatörsalgoritm

Länkar

Ordböcker och uppslagsverk	Stor ryss