Normal algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 10. november 2021; checks kræver 2 redigeringer .

En normal algoritme (algoritme) af Markov ( NAM , også en Markov-algoritme ) er en af standardmåderne til formelt at definere begrebet en algoritme (en anden velkendt metode er en Turing-maskine ). Begrebet en normal algoritme blev introduceret af A. A. Markov (junior) i slutningen af 1940'erne i værker om uløseligheden af nogle problemer i teorien om associative beregninger. Den traditionelle stavemåde og udtale af ordet "algori f m" i dette udtryk går også tilbage til dets forfatter, som i mange år underviste i et kursus i matematisk logik ved Fakultetet for Mekanik og Matematik ved Moskva State University .

Den normale algoritme beskriver en metode til omskrivning af strenge, på samme måde som formelle grammatikker . NAM er et Turing-komplet sprog, hvilket gør det svarende i udtrykskraft til en Turing-maskine og derfor til moderne programmeringssprog. Det funktionelle programmeringssprog Refal blev skabt på basis af NAM .

Beskrivelse

Normale algoritmer er verbale, det vil sige, at de er beregnet til at blive anvendt på ord i forskellige alfabeter.

Definitionen af enhver normal algoritme består af to dele: definitionen af algoritmens alfabet (til de ord, fra hvis tegn algoritmen vil blive anvendt) og definitionen af dens skema . Skemaet for en normal algoritme er et endeligt ordnet sæt af såkaldte substitutionsformler , som hver kan være enkle eller endelige . Simple substitutionsformler er ord af formen , hvor og er to vilkårlige ord i algoritmens alfabet (kaldet henholdsvis venstre og højre side af substitutionsformlen). Tilsvarende er de endelige substitutionsformler ord af formen , hvor og er to vilkårlige ord i algoritmens alfabet. Det antages, at hjælpebogstaverne og ikke tilhører alfabetet af algoritmen (ellers skal to andre bogstaver vælges til at spille rollen som en separator mellem venstre og højre del). $L til D$ $L$ $D$ $L\til \cdot D$ $L$ $D$ $\til$ $\til \cdot$

Et eksempel på et normalt algoritmeskema i et alfabet på fem bogstaver er skemaet $|*abc$

$\venstre\{{\begin{matrix}|b&\til &ba|\\ab&\til &ba\\b&\til &\\{*}|&\til &b*&\\{*}&\til &c&\ \|c&\til &c\\ac&\to &c|\\c&\til \cdot \end{matrix}}\right.$

Processen med at anvende den normale algoritme på et vilkårligt ord i alfabetet af denne algoritme er en diskret sekvens af elementære trin, der består af følgende. Lad være ordet opnået i det foregående trin i algoritmen (eller det originale ord, hvis det aktuelle trin er det første). Hvis der blandt substitutionsformlerne ikke er nogen, hvis venstre side ville være inkluderet i , anses algoritmens arbejde for at være afsluttet, og resultatet af dette arbejde er ordet . Ellers, blandt substitutionsformlerne, hvis venstre del er inkluderet i , er den allerførste valgt. Hvis denne substitutionsformel har formen , så vælges ud af alle mulige repræsentationer af ordet i formen en, som er den korteste, hvorefter algoritmen anses for at være afsluttet med resultatet . Hvis denne substitutionsformel har formen , så vælges fra alle mulige repræsentationer af ordet i formen den, som er den korteste, hvorefter ordet betragtes som resultatet af det aktuelle trin, med forbehold for yderligere behandling ved det næste trin. $V$ $V'$ $V$ $V'$ $V'$ $V'$ $L\til \cdot D$ $V'$ $RLS$ $R$ $RDS$ $L til D$ $V'$ $RLS$ $R$ $RDS$

For eksempel, i løbet af processen med at anvende algoritmen med skemaet angivet ovenfor , vises ordene , , , , , , , , og sekventielt til ordet , hvorefter algoritmen afsluttes med resultatet . Se flere eksempler nedenfor. $|*||$ $|b*|$ $ba|*|$ $a|*|$ $a|b*$ $aba|*$ $baa|*$ $aa|*$ $aa|c$ $aac$ $ac|$ $c||$ $||$

Enhver normal algoritme svarer til en Turing-maskine , og omvendt, enhver Turing-maskine svarer til en normal algoritme. En variant af Church-Turing-afhandlingen , formuleret i forhold til normale algoritmer, kaldes almindeligvis "normaliseringsprincippet".

Normale algoritmer har vist sig at være et praktisk værktøj til at konstruere mange grene af konstruktiv matematik . Derudover bruges ideerne i definitionen af den normale algoritme i en række programmeringssprog orienteret til behandling af symbolsk information - for eksempel i Refal- sproget .

Eksempler

Eksempel 1

Brug af Markov-algoritmen til transformationer på strenge.

Alfabet:

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

Regler:

A → orange
kg til kilogram
M → butik
T → volumen
butik →. stall (endelig formel)
i den bod → på det marked

Kildelinje:

Jeg købte kg Aov i TM.

Når algoritmen udføres, gennemgår strengen følgende ændringer:

Jeg købte et kg appelsiner hos TM.
Jeg købte et kilo appelsiner hos T.M.
Jeg købte et kilo appelsiner i T-shoppen.
Jeg købte et kilo appelsiner i den butik.
Jeg købte et kilo appelsiner i den bod.

Dette fuldender eksekveringen af algoritmen (da formel nr. 5, som vi gjorde endelig, nås).

Eksempel 2

Denne algoritme konverterer binære tal til " single " (hvor posten af et ikke-negativt heltal N er en streng af N pinde). For eksempel konverteres det binære tal 101 til 5 pinde: |||||.

Alfabet:

{ 0, 1, | }

Regler:

1 → 0|
|0 → 0||
0 → "" (tom streng)

Kildelinje:

101

Ydeevne:

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

Se også

Andre abstrakte implementere og formelle computersystemer

Sprog baseret på normale algoritmer

REFAL
Thue

Andre algoritmer

Operatør algoritme

Links

Ordbøger og encyklopædier	Stor russer