Algoritmkarakteriseringar

Den här artikeln är ett komplement till artikeln Algoritm .

Algoritmkarakteriseringar är försök att formalisera ordet algoritm . Algoritmen har ingen allmänt accepterad formell definition. Forskare arbetar aktivt med detta problem. Den här artikeln kommer att presentera några av "karakteriseringarna" av begreppet "algoritm" mer i detalj.

Definitionsproblemet

Under de senaste 200 åren har definitionen av algoritm blivit mer komplicerad och detaljerad eftersom forskare har försökt slå fast termen. Det kan faktiskt finnas mer än en typ av "algoritm". Men de flesta är överens om att algoritmen har något att göra med att definiera generaliserade processer för att skapa "output"-heltal från andra "input"-heltal – "inputparametrar" godtyckliga och oändliga i omfattning, eller begränsade i omfattning men fortfarande varierande - genom manipulering av särskiljbara symboler (räknetal) med ändliga samlingar av regler som en person kan utföra med papper och penna.

De vanligaste siffermanipulationsschemana – både i formell matematik och i rutinlivet – är: (1) de rekursiva funktionerna beräknade av en person med papper och penna, och (2) Turingmaskinen eller dess Turing-ekvivalenter – det primitiva registret- maskin- eller "counter-machine"-modellen, RAM-modellen ( Random-Access Machine Model), RASP (Random-Access Stored-Program Machine Model) och dess funktionella motsvarighet "datorn " .

När vi håller på med "aritmetik" räknar vi verkligen genom att använda "rekursiva funktioner" i de stenografialgoritmer vi lärde oss i grundskolan, till exempel genom att addera och subtrahera.

Bevisen för att varje "rekursiv funktion" vi kan beräkna för hand kan beräkna med maskin och vice versa - notera användningen av orden beräkna mot beräkna - är anmärkningsvärda. Men denna likvärdighet tillsammans med tesen (obevisat påstående) att detta inkluderar varje beräkning/beräkning indikerar varför så mycket tonvikt har lagts på användningen av Turing-ekvivalenta maskiner i definitionen av specifika algoritmer, och varför själva definitionen av "algoritm" refererar ofta tillbaka till " Turing-maskinen ". Detta diskuteras mer i detalj under Stephen Kleenes karaktärisering .

Följande är sammanfattningar av de mer kända karaktäriseringarna (Kleene, Markov, Knuth) tillsammans med de som introducerar nya element - element som ytterligare utökar definitionen eller bidrar till en mer exakt definition.

[ Ett matematiskt problem och dess resultat kan betraktas som två punkter i ett rum, och lösningen består av en sekvens av steg eller en väg som länkar dem. Kvaliteten på lösningen är en funktion av vägen. Det kan finnas mer än ett attribut definierat för sökvägen, t.ex. längd, formens komplexitet, lätthet att generalisera, svårighetsgrad och så vidare . ]

Chomsky hierarki

Det finns mer konsensus om "karakteriseringen" av begreppet "enkel algoritm".

Alla algoritmer måste specificeras på ett formellt språk, och "enkelhetsbegreppet" uppstår från språkets enkelhet. Chomsky (1956) hierarki är en inneslutningshierarki av klasser av formella grammatiker som genererar formella språk . Den används för klassificering av programmeringsspråk och abstrakta maskiner .

Ur Chomsky- hierarkiperspektivet, om algoritmen kan specificeras på ett enklare språk (än obegränsat), kan den karakteriseras av denna typ av språk, annars är det en typisk "obegränsad algoritm".

Exempel: ett makrospråk för "allmänt bruk", som M4 , är obegränsat ( Turing komplett ), men makrospråket för C-förprocessorn är det inte, så alla algoritmer som uttrycks i C-förprocessorer är en "enkel algoritm".

Se även Relationer mellan komplexitetsklasser .

Funktioner hos en bra algoritm

Följande är önskvärda egenskaper hos en väldefinierad algoritm, som diskuteras i Scheider och Gersting (1995):

  • Entydiga operationer: en algoritm måste ha specifika, skisserade steg. Stegen bör vara tillräckligt exakta för att exakt specificera vad som ska göras vid varje steg.
  • Välordnad: Den exakta ordningen för operationer som utförs i en algoritm bör definieras konkret.
  • Genomförbarhet: Alla steg i en algoritm bör vara möjliga (även känd som effektivt beräkningsbar ).
  • Indata: en algoritm ska kunna acceptera en väldefinierad uppsättning indata.
  • Utdata: en algoritm bör producera något resultat som en utdata, så att dess riktighet kan resoneras om.
  • Finitet: en algoritm ska avslutas efter ett begränsat antal instruktioner.

Egenskaper för specifika algoritmer som kan vara önskvärda inkluderar rums- och tidseffektivitet , generalitet (dvs att kunna hantera många indata) eller determinism .

1881 John Venns negativa reaktion på W. Stanley Jevons Logical Machine från 1870

I början av 1870 presenterade W. Stanley Jevons en "Logical Machine" (Jevons 1880:200) för att analysera en syllogism eller annan logisk form , t.ex. ett argument reducerat till en boolesk ekvation . Med hjälp av vad Couturat (1914) kallade ett "slags logiskt piano [,] ... "spelas" de jämlikheter som representerar lokalerna ... på ett tangentbord som på en skrivmaskin ... När alla lokaler har "spelats", visar panelen endast de beståndsdelar vars summa är lika med 1, det vill säga ... dess logiska helhet. Denna mekaniska metod har fördelen framför VENN:s geometriska metod..." (Couturat 1914:75).

För sin del var John Venn , en logiker samtida med Jevons, mindre än förtjust och menade att "det förefaller mig inte som att några konstigheter som för närvarande är kända eller sannolikt kommer att upptäckas verkligen förtjänar namnet logiska maskiner" (kursiv stil, Venn 1881:120). Men till historisk nytta för den utvecklande begreppet "algoritm" är hans förklaring till hans negativa reaktion med avseende på en maskin som "kan tjäna ett riktigt värdefullt syfte genom att göra det möjligt för oss att undvika annars oundvikligt arbete":

(1) "Det finns, för det första, redogörelsen för våra data på ett korrekt logiskt språk", (
2) "Sen för det andra måste vi kasta dessa uttalanden i en form som passar motorn att arbeta med – i det här fallet minskningen av varje förslag till dess elementära förnekelser",
(3) "För det tredje finns det kombinationen eller ytterligare behandling av våra lokaler efter en sådan minskning," (
4) "Slutligen måste resultaten tolkas eller läsas av. Detta sista ger i allmänhet upphov till för mycket öppning för skicklighet och klokhet."

Han drar slutsatsen att "Jag kan inte se att någon maskin kan hoppas på att hjälpa oss utom i det tredje av dessa steg, så att det verkar mycket tveksamt om något av detta slag verkligen förtjänar namnet på en logisk motor." (Venn 1881:119) –121).

1943, 1952 Stephen Kleenes karaktärisering

Det här avsnittet är längre och mer detaljerat än de andra på grund av dess betydelse för ämnet: Kleene var den första som föreslog att alla beräkningar/beräkningar – av alla slag, helheten av – på motsvarande sätt kan (i) beräknas med hjälp av fem " primitiva rekursiva operatörer" plus en speciell operatör som kallas mu-operator , eller (ii) beräknas av åtgärderna från en Turing-maskin eller en motsvarande modell.

Dessutom ansåg han att någon av dessa skulle stå som en definition av algoritm .

En läsare som först konfronterar orden som följer kan mycket väl bli förvirrad, så en kort förklaring är på sin plats. Beräkning betyder för hand, beräkning görs av Turing-maskin (eller motsvarande). (Ibland halkar en författare och byter ut orden). En "funktion" kan ses som en "input-output box" i vilken en person lägger naturliga tal som kallas "argument" eller "parametrar" (men bara de räknande talen inklusive 0 - de icke-negativa heltalen) och får ut ett enda icke-negativt tal. heltal (kallas konventionellt "svaret"). Tänk på "funktionslådan" som en liten man som antingen räknar för hand med hjälp av "allmän rekursion" eller beräknar med Turing-maskin (eller motsvarande maskin).

"Efektivt beräkningsbar/beräknbar" är mer generisk och betyder "beräknbar/beräknbar med någon procedur, metod, teknik ... vad som helst...". "Allmänt rekursivt" var Kleenes sätt att skriva det som idag kallas för just "rekursion"; emellertid är "primitiv rekursion" – beräkning med hjälp av de fem rekursiva operatorerna – en mindre form av rekursion som saknar tillgång till den sjätte, ytterligare mu-operatorn som endast behövs i sällsynta fall. Sålunda fortsätter det mesta av livet och kräver endast de "primitiva rekursiva funktionerna".

1943 "Thesis I", 1952 "Church's Thesis"

1943 föreslog Kleene vad som har kommit att kallas kyrkans tes :

" Tesis I. Varje effektivt beräkningsbar funktion (effektivt avgörbart predikat) är generellt rekursiv" (Först uttalad av Kleene 1943 (omtryckt sida 274 i Davis, ed. The Undecidable ; förekommer också ordagrant i Kleene (1952) s.300)

I ett nötskal: för att beräkna vilken funktion som helst är de enda operationerna en person behöver (tekniskt, formellt) de 6 primitiva operatorerna för "allmän" rekursion (nuförtiden kallas operatorerna för mu- rekursiva funktioner ).

Kleenes första uttalande om detta var under rubriken " 12. Algoritmiska teorier ". Han skulle senare förstärka det i sin text (1952) på följande sätt:

"Tes I och dess motsats ger den exakta definitionen av begreppet en beräknings(beslut)procedur eller algoritm , för fallet med en funktion (predikat) av naturliga tal" (s. 301, fetstil tillagd för betoning)

(Hans användning av ordet "beslut" och "predikat" utvidgar begreppet beräkningsbarhet till den mer allmänna manipulationen av symboler, såsom förekommer i matematiska "bevis".)

Detta är inte så skrämmande som det kan låta – "allmän" rekursion är bara ett sätt att göra våra vardagliga aritmetiska operationer från de fem "operatorerna" av de primitiva rekursiva funktionerna tillsammans med den extra mu-operatorn efter behov. Kleene ger faktiskt 13 exempel på primitiva rekursiva funktioner och Boolos–Burgess–Jeffrey lägger till några till, varav de flesta kommer att vara bekanta för läsaren – t.ex. addition, subtraktion, multiplikation och division, exponentiering, CASE-funktionen, sammanlänkning, etc., etc.; för en lista se Några vanliga primitiva rekursiva funktioner .

Varför generell-rekursiva funktioner snarare än primitiva-rekursiva funktioner?

Kleene et al. (jfr §55 Allmänna rekursiva funktioner s. 270 i Kleene 1952) var tvungen att lägga till en sjätte rekursionsoperator som kallas minimeringsoperator (skriven som μ-operator eller mu-operator ) eftersom Ackermann (1925) producerade en enormt växande funktion - Ackermann funktion — och Rózsa Péter (1935) tog fram en allmän metod för att skapa rekursiva funktioner med hjälp av Cantors diagonala argument , ingen av dem kunde beskrivas av de 5 primitiva-rekursiva-funktionsoperatorerna. När det gäller Ackermann-funktionen:

"...i en viss mening växer längden på beräkningsalgoritmen för en rekursiv funktion som inte också är primitiv rekursiv snabbare med argumenten än värdet på någon primitiv rekursiv funktion" (Kleene (1935) återgiven s. 246 i The Obestämbart , plus fotnot 13 angående behovet av ytterligare en operatör, fetstil tillagd).

Men behovet av mu-operatören är en sällsynthet. Som indikeras ovan av Kleenes lista över vanliga beräkningar, fortsätter en person med glädje i sitt liv och beräknar primitiva rekursiva funktioner utan rädsla för att möta monstertalen som skapas av Ackermanns funktion (t.ex. superexponentiering ) .

1952 "Turings avhandling"

Turings avhandling ger en hypotes om beräkningsbarheten av "alla beräkningsbara funktioner" av Turingmaskinmodellen och dess motsvarigheter.

För att göra detta på ett effektivt sätt utvidgade Kleene begreppet "beräknarbar" genom att göra nätet bredare - genom att tillåta begreppet "funktioner" både "totala funktioner" och "delfunktioner". En totalfunktion är en som definieras för alla naturliga tal (positiva heltal inklusive 0). En delfunktion definieras för vissa naturliga tal men inte alla – specifikationen för "några" måste komma "framtill". Sålunda utökar inkluderingen av "delfunktion" begreppet funktion till "mindre perfekta" funktioner. Total- och delfunktioner kan antingen beräknas för hand eller beräknas med maskin.

Exempel:
"Funktioner": inkluderar "gemensam subtraktion m − n " och "addition m + n "
"Partialfunktion": "Gemensam subtraktion" m − n är odefinierad när endast naturliga tal (positiva heltal och noll) är tillåtna som indata – t.ex. 6 − 7 är odefinierad
Total funktion: "Addition" m + n definieras för alla positiva heltal och noll.


Vi observerar nu Kleenes definition av "beräknarbar" i en formell mening:

Definition: "En partiell funktion φ är beräkningsbar , om det finns en maskin M som beräknar den" (Kleene (1952) s. 360) "
Definition 2.5. En n -är funktion f ( x 1 , ..., x n ) är delvis beräkningsbar om det finns en Turingmaskin Z så att
f ( x 1 , ..., x n ) = Ψ Z ( n ) ( x 1 , ..., [ x n )
I det här fallet säger vi att [maskin ] Z beräknar f . Om dessutom f ( x 1 , ..., x n ) är en totalfunktion, så kallas den beräkningsbar " (Davis (1958) s. 10)

Så har vi kommit fram till Turings avhandling :

"Varje funktion som naturligt skulle betraktas som beräkningsbar är beräkningsbar ... av en av hans maskiner ..." (Kleene (1952) s.376)

Även om Kleene inte gav exempel på "beräknarbara funktioner" andra har. Davis (1958) ger till exempel Turing-tabeller för funktionerna konstant, efterföljare och identitet, tre av de fem operatorerna för de primitiva rekursiva funktionerna :

Beräkningsbar av Turing-maskin:
Addition (är även konstantfunktionen om en operand är 0)
Inkrement (Efterföljarefunktion)
Gemensam subtraktion (definieras endast om x ≥ y ). Således är " x − y " ett exempel på en delvis beräkningsbar funktion.
Korrekt subtraktion x ┴ y (enligt definitionen ovan)
Identitetsfunktionen: för varje i finns en funktion U Z n = Ψ Z n ( x 1 , ..., x n ) som plockar x i ur uppsättningen argument ( x 1 , ..., x n )
Multiplikation

Boolos–Burgess–Jeffrey (2002) ger följande som prosabeskrivningar av Turing-maskiner för:

Fördubbling p
:
2
Paritetsadditionsmultiplikation

När det gäller diskmaskinen , en abstrakt maskinmodell motsvarande Turing-maskinen:

Exempel som kan beräknas av Abacus-maskin (jfr Boolos–Burgess–Jeffrey (2002))
Additionsmultiplikationsexponention
:
(ett flödesschema/blockdiagrambeskrivning av algoritmen)

Demonstrationer av beräkningsbarhet med abacusmaskin (Boolos–Burgess–Jeffrey (2002)) och med räknarmaskin (Minsky 1967):

De sex rekursiva funktionsoperatorerna:
  1. Noll funktion
  2. Efterträdarfunktion
  3. Identitetsfunktion
  4. Kompositionsfunktion
  5. Primitiv rekursion (induktion)
  6. Minimering

Det faktum att abacus/ motmaskinmodellerna kan simulera de rekursiva funktionerna ger beviset att: Om en funktion är "maskinberäknbar" så är den "handberäknbar genom partiell rekursion". Kleenes sats XXIX:

" Sats XXIX: "Varje beräkningsbar partiell funktion φ är partiell rekursiv... " (kursiv stil i original, s. 374).

Det omvända framstår som hans sats XXVIII. Tillsammans bildar dessa beviset på deras likvärdighet, Kleenes sats XXX.

1952 Church–Turing-avhandling

Med sin sats XXX bevisar Kleene att de två "teserna" är likvärdiga - Kyrkans avhandling och Turingtesen. (Kleene kan bara anta (gissningar) sanningen i båda teserna – dessa har han inte bevisat ):

SAT XXX: Följande klasser av partiella funktioner ... har samma medlemmar: (a) de partiella rekursiva funktionerna, (b) de beräkningsbara funktionerna ..." (s. 376) Definition av
"partiell rekursiv funktion": "A partialfunktion φ är partiell rekursiv i [delfunktionerna] ψ 1 , ... ψ n om det finns ett ekvationssystem E som definierar φ rekursivt från [partialfunktioner] ψ 1 , ... ψ n " (s. 326) )

Således av Kleenes sats XXX: endera metoden att göra tal från inmatade tal – rekursiva funktioner beräknade för hand eller beräknade av Turing-maskin eller motsvarande – resulterar i en "effektivt beräkningsbar/beräknbar funktion". Om vi ​​accepterar hypotesen att varje beräkning/beräkning kan göras med endera metoden på motsvarande sätt har vi accepterat både Kleenes sats XXX (ekvivalensen) och Church –Turing-tesen (hypotesen om "varje").

En notering av oliktänkande: "Det finns mer i algoritmen..." Blass och Gurevich (2003)

Föreställningen att separera Churchs och Turings teser från "Church–Turing-tesen" förekommer inte bara i Kleene (1952) utan även i Blass-Gurevich (2003). Men även om det finns överenskommelser finns det också oenigheter:

"...vi håller inte med Kleene om att begreppet algoritm är så väl förstått. Faktum är att begreppet algoritm är rikare nuförtiden än det var på Turings dagar. Och det finns algoritmer, av moderna och klassiska varianter, som inte täcks direkt av Turings analys, till exempel, algoritmer som interagerar med sina miljöer, algoritmer vars indata är abstrakta strukturer och geometriska eller, mer allmänt, icke-diskreta algoritmer" (Blass-Gurevich (2003) s. 8, fetstil tillagd)

1954 AA Markov Jrs karaktärisering

Andrey Markov Jr. (1954) gav följande definition av algoritm:

"1. I matematik förstås "algoritm" vanligtvis som ett exakt recept, som definierar en beräkningsprocess, som leder från olika initiala data till det önskade resultatet..." "Följande tre
egenskaper är karakteristiska för algoritmer och bestämmer deras roll i matematik:
"a) precisionen av receptet, som inte lämnar någon plats åt godtycke, och dess universella begriplighet - algoritmens definitiitet;
"b) möjligheten att börja med initiala data, som kan variera inom givna gränser - algoritmens generella karaktär; "c)
orienteringen av algoritmen mot att erhålla något önskat resultat, vilket verkligen erhålls i slutändan med korrekt initial data -- algoritmens slutgiltighet." (s.1)

Han medgav att denna definition "inte utger sig för matematisk precision" (s. 1). Hans monografi från 1954 var hans försök att definiera algoritmen mer exakt; han såg sin resulterande definition - hans "normala" algoritm - som "likvärdig med begreppet en rekursiv funktion " (s. 3). Hans definition inkluderade fyra huvudkomponenter (kapitel II.3 s. 63ff):

"1. Separata elementära steg, som vart och ett kommer att utföras enligt en av [ersättningsreglerna]... [regler som ges i början] "
2. ... steg av lokal natur ... [Algorithmen kommer alltså inte att ändra mer än ett visst antal symboler till vänster eller höger om det observerade ordet/symbolen] "3.
Regler för substitutionsformlerna ... [han kallade listan över dessa "schemat" för algoritmen] "
4. ...ett sätt att särskilja en "avslutande substitution" [dvs en särskiljbar "terminal/slutlig" stat eller stater]

I sin inledning observerade Markov att "hela betydelsen för matematiken" av ansträngningar att definiera algoritmer mer exakt skulle vara "i samband med problemet med en konstruktiv grund för matematik" (s. 2). Ian Stewart (jfr Encyclopædia Britannica) delar en liknande uppfattning: "...konstruktiv analys är mycket i samma algoritmiska anda som datavetenskap...". För mer se konstruktiv matematik och intuitionism .

Särskiljbarhet och lokalitet : Båda begreppen dök upp först med Turing (1936–1937) --

"De nya observerade kvadraterna måste omedelbart kännas igen av datorn [ sic : en dator var en person 1936]. Jag tycker det är rimligt att anta att de bara kan vara kvadrater vars avstånd från närmaste av de omedelbart observerade kvadraterna inte överstiger en visst fast belopp. Låt oss hålla fast vid att var och en av de nya observerade kvadraterna är inom L kvadrater från en av de tidigare observerade kvadraterna." (Turing (1936) s. 136 i Davis ed. Undecidable )

Lokalitet framträder framträdande i arbetet av Gurevich och Gandy (1980) (som Gurevich citerar). Gandys "fjärde princip för mekanismer" är "principen om lokal kausalitet":

"Vi kommer nu till de viktigaste av våra principer. I Turings analys baseras kravet på att handlingen endast beror på en avgränsad del av dokumentet på en mänsklig begränsning. Vi ersätter detta med en fysisk begränsning som vi kallar principen om lokal orsakssamband. Dess motivering ligger i den ändliga hastigheten för utbredning av effekter och signaler: samtida fysik avvisar möjligheten till omedelbar verkan på avstånd." (Gandy (1980) s. 135 i J. Barwise et al.)

1936, 1963, 1964 Gödels karaktärisering

1936 : Ett ganska berömt citat från Kurt Gödel förekommer i en "anmärkning som läggs till som bevis [för den ursprungliga tyska publikationen] i hans tidning "On the Length of Proofs" översatt av Martin Davis som förekommer på s. 82–83 i The Undecidable . A antal författare – Kleene, Gurevich, Gandy etc. – har citerat följande:

"Alltså är begreppet "beräknarbar" i en viss bestämd mening "absolut", medan praktiskt taget alla andra välbekanta metamatematiska begrepp (t.ex. bevisbara, definierbara, etc.) är ganska väsentligt beroende av systemet med avseende på vilket de definieras." (sid. 83)

1963 : I en "anteckning" daterad den 28 augusti 1963 som lades till i hans berömda artikel On Formally Undecidable Propositions (1931) anger Gödel (i en fotnot) sin övertygelse att " formella system " har "den karakteristiska egenskapen att resonemang i dem, i princip, kan helt ersättas av mekaniska anordningar" (s. 616 i van Heijenoort). "... på grund av "AM Turings arbete kan nu ges en exakt och otvivelaktigt adekvat definition av det allmänna begreppet formellt system [och] en helt allmän version av satser VI och XI är nu möjlig." (s. 616). I en anteckning från 1964 till ett annat verk uttrycker han samma åsikt starkare och mer detaljerat.

1964 : I ett Postscriptum, daterat 1964, till en artikel som presenterades för Institutet för avancerade studier våren 1934, förstärkte Gödel sin övertygelse om att "formella system" är de som kan mekaniseras:

"Till följd av senare framsteg, i synnerhet av det faktum att, på grund av AM Turings arbete, en exakt och otvivelaktigt adekvat definition av det allmänna begreppet formellt system nu kan ges... Turings arbete ger en analys av begreppet " mekanisk procedur" (alias "algoritm" eller "beräkningsprocedur" eller "ändlig kombinatorisk procedur"). Detta koncept har visat sig vara likvärdigt med det för en "turingmaskin".* Ett formellt system kan helt enkelt definieras som vilken mekanisk procedur som helst. för att producera formler, så kallade bevisbara formler ...." (s. 72 i Martin Davis ed. The Undecidable : "Postscriptum" till "On Undecidable Propositions of Formal Mathematical Systems" som visas på sid. 39, loc. cit.)

* anger en fotnot där Gödel citerar tidningarna av Alan Turing (1937) och Emil Post (1936) och sedan fortsätter med att göra följande spännande uttalande:

"När det gäller tidigare likvärdiga definitioner av beräkningsbarhet, som dock är mycket mindre lämpliga för vårt syfte, se Alonzo Church , Am. J. Math., vol. 58 (1936) [uppträder i The Undecidable s. 100-102]).

Kyrkans definitioner omfattar så kallad " rekursion " och " lambdakalkylen " (dvs. de λ-definierbara funktionerna). Hans fotnot 18 säger att han diskuterade förhållandet "effektiv beräkningsbarhet" och "rekursivitet" med Gödel men att han självständigt ifrågasatte "effektiv beräkningsbarhet" och "λ-definierbarhet":

"Vi definierar nu begreppet ... av en effektivt beräkningsbar funktion av positiva heltal genom att identifiera den med begreppet en rekursiv funktion av positiva heltal 18 (eller av en λ-definierbar funktion av positiva heltal. "
Det har redan påpekats att det för varje funktion av positiva heltal som är effektivt beräkningsbar i den bemärkelse som just definierats, det finns en algoritm för beräkning av dess värde: "
Omvänt är det sant..." (s. 100, The Unecidable).

Av detta och följande framgår att vad Gödel beträffar var Turingmaskinen tillräcklig och lambdakalkylen "mycket mindre lämplig". Han fortsätter med att påpeka att, när det gäller begränsningar av mänskligt förnuft, är juryn fortfarande ute:

("Notera att frågan om det finns ändliga icke-mekaniska procedurer** som inte är likvärdiga med någon algoritm, inte har något som helst att göra med adekvatheten av definitionen av "formellt system" och av "mekanisk procedur.") (s. 72, loc. cit.)
"(För teorier och förfaranden i den mer allmänna meningen som anges i fotnot ** kan situationen vara annorlunda. Observera att resultaten som nämns i efterskriften inte sätter några gränser för det mänskliga förnuftets befogenheter, men snarare för potentialen hos ren formalism i matematik.) (s. 73 loc. cit.)
Fotnot **: "Dvs sådana som involverar användningen av abstrakta termer på grundval av deras betydelse. Se min artikel i Dial. 12( 1958), s. 280." (denna fotnot finns på s. 72, cit. cit.).

1967 Minskys karaktärisering

Minsky (1967) hävdar rakt av att "en algoritm är "en effektiv procedur" och avböjer att använda ordet "algoritm" längre fram i sin text; i själva verket gör hans index tydligt vad han tycker om "Algorithm, synonym för effektiv procedur " ( s. 311):

"Vi kommer att använda den senare termen [en effektiv procedur ] i uppföljaren. Termerna är ungefär synonyma, men det finns ett antal betydelsenyanser som används i olika sammanhang, särskilt för 'algoritm'" (kursiv i original, s. 105) )

Andra skribenter (se Knuth nedan) använder ordet "effektivt förfarande". Detta får en att undra: Vad är Minskys uppfattning om "ett effektivt förfarande"? Han börjar med:

"...en uppsättning regler som talar om för oss, från ögonblick till ögonblick, exakt hur vi ska bete oss" (s. 106)

Men han inser att detta är föremål för kritik:

"... kritiken att tolkningen av reglerna lämnas att bero på någon person eller agent" (s. 106)

Hans förfining? Att "specificera, tillsammans med uttalandet av reglerna, detaljerna i mekanismen som ska tolka dem" . För att undvika den "krångliga" processen att "måste göra om detta för varje enskild procedur" hoppas han kunna identifiera en "rimligen enhetlig familj av regellydande mekanismer". Hans "formulering":

"(1) ett språk på vilket uppsättningar av beteenderegler ska uttryckas, och
"(2) en enda maskin som kan tolka uttalanden på språket och därmed utföra stegen i varje specificerad process." (kursiv stil i original, alla citerar denna paragraf s. 107)

Men i slutändan oroar han sig fortfarande för att "det kvarstår en subjektiv aspekt av saken. Olika människor kanske inte är överens om huruvida ett visst förfarande ska kallas effektivt" (s. 107)

Men Minsky är inte avskräckt. Han introducerar omedelbart "Turings analys av beräkningsprocessen" (hans kapitel 5.2). Han citerar vad han kallar "Turings tes "

"Varje process som naturligt skulle kunna kallas en effektiv procedur kan realiseras av en Turing-maskin" (s. 108. (Minsky kommenterar att detta i en mer allmän form kallas " Kyrkans tes" ).

Efter en analys av "Turings argument" (hans kapitel 5.3) observerar han att "motsvarigheten av många intuitiva formuleringar" av Turing, Church, Kleene, Post och Smullyan "... leder oss att anta att det verkligen finns här ett "mål" ' eller 'absolut' begrepp. Som Rogers [1959] uttryckte det:

"I denna mening är begreppet effektivt beräkningsbar funktion ett av de få 'absoluta' begrepp som produceras av modernt arbete i grunderna för matematik" (Minsky s. 111 citerar Rogers, Hartley Jr (1959) The present theory of Turing machine beräkningsbarhet , J. SIAM 7, 114-130.)

1967 Rogers karaktärisering

I sin Theory of Recursive Functions and Effective Computability från 1967 karakteriserar Hartley Rogers "algoritm" ungefär som "en klerikal (dvs. deterministisk, bokföring) procedur ... tillämpad på ... symboliska indata och som så småningom kommer att ge, för varje sådan ingång , en motsvarande symbolisk utgång "(sid. 1). Han fortsätter sedan med att beskriva begreppet "i ungefärliga och intuitiva termer" som att det har 10 "funktioner", 5 av vilka han hävdar att "i stort sett alla matematiker skulle gå med på [att]" (s. 2). De återstående 5 hävdar han "är mindre uppenbara än *1 till *5 och om vilka vi kan finna mindre allmän överenskommelse" (s. 3).

De 5 "uppenbara" är:

  • 1 En algoritm är en uppsättning instruktioner av ändlig storlek,
  • 2 Det finns en kapabel datoragent,
  • 3 "Det finns faciliteter för att göra, lagra och hämta steg i en beräkning"
  • 4 Givet #1 och #2 beräknar agenten på "diskret stegvis sätt" utan användning av kontinuerliga metoder eller analoga enheter",
  • 5 Datoragenten för beräkningen vidare "utan att tillgripa slumpmässiga metoder eller enheter, t.ex. tärningar" (i en fotnot undrar Rogers om #4 och #5 verkligen är samma sak)

De återstående 5 som han öppnar för debatt är:

  • 6 Ingen fast gräns för storleken på ingångarna,
  • 7 Ingen fast gräns för storleken på uppsättningen instruktioner,
  • 8 Ingen fast gräns för mängden tillgängligt minne,
  • 9 En fast ändlig gräns för kapaciteten eller förmågan hos beräkningsagenten (Rogers illustrerar med exempel enkla mekanismer som liknar en Post-Turing-maskin eller en motmaskin ),
  • 10 A gräns för längden på beräkningen -- "ska vi ha någon aning, 'i förväg', hur lång tid beräkningen kommer att ta?" (sid. 5). Rogers kräver "bara att en beräkning avslutas efter ett ändligt antal steg; vi insisterar inte på en a priori förmåga att uppskatta detta antal." (sid. 5).

1968, 1973 Knuths karaktärisering

Knuth (1968, 1973) har gett en lista över fem egenskaper som är allmänt accepterade som krav för en algoritm:

  1. Finiteness : "En algoritm måste alltid avslutas efter ett ändligt antal steg ... ett mycket ändligt antal, ett rimligt antal"
  2. Säkerhet : "Varje steg i en algoritm måste definieras exakt; de åtgärder som ska utföras måste vara strikt och entydigt specificerade för varje fall"
  3. Input : "...kvantiteter som ges till den initialt innan algoritmen börjar. Dessa indata hämtas från specificerade uppsättningar objekt"
  4. Output : "...kvantiteter som har en specificerad relation till ingångarna"
  5. Effektivitet : "... alla operationer som ska utföras i algoritmen måste vara tillräckligt grundläggande för att de i princip kan utföras exakt och på en begränsad tid av en man som använder papper och penna"

Knuth erbjuder som exempel den euklidiska algoritmen för att bestämma den största gemensamma delaren av två naturliga tal (jfr Knuth Vol. 1 s. 2).

Knuth medger att även om hans beskrivning av en algoritm kan vara intuitivt tydlig, saknar den formell rigor, eftersom det inte är exakt klart vad "precis definierad" betyder, eller "rigoröst och otvetydigt specificerad" betyder, eller "tillräckligt grundläggande", och så vidare. Han anstränger sig i denna riktning i sin första volym där han i detalj definierar vad han kallar " maskinspråket " för sin "mytiska MIX ... världens första fleromättade dator" (s. 120ff). Många av algoritmerna i hans böcker är skrivna på MIX-språket. Han använder också träddiagram , flödesdiagram och tillståndsdiagram .

"Godhet" hos en algoritm, "bästa" algoritmer : Knuth säger att "I praktiken vill vi inte bara ha algoritmer, vi vill ha bra algoritmer...." Han föreslår att några kriterier för en algoritms godhet är antalet steg som ska utföras algoritmen, dess "anpassningsförmåga till datorer, dess enkelhet och elegans, etc." Med tanke på ett antal algoritmer för att utföra samma beräkning, vilken är "bäst"? Han kallar denna typ av undersökning "algoritmisk analys: given en algoritm, för att bestämma dess prestandaegenskaper" (alla citerar detta stycke: Knuth Vol. 1 s. 7)

1972 Stones karaktärisering

Stone (1972) och Knuth (1968, 1973) var professorer vid Stanford University samtidigt så det är inte förvånande om det finns likheter i deras definitioner (fetstil lagt till för att betona):

"För att sammanfatta ... definierar vi en algoritm som en uppsättning regler som exakt definierar en sekvens av operationer så att varje regel är effektiv och bestämd och så att sekvensen avslutas i en ändlig tid." (fetstil tillagd, s. 8)

Stone är anmärkningsvärd på grund av hans detaljerade diskussion om vad som utgör en "effektiv" regel - hans robot , eller person som agerar-som-robot, måste ha viss information och förmågor inom sig, och om inte måste informationen och förmågan tillhandahållas i "algoritmen":

"För att människor ska följa reglerna för en algoritm måste reglerna formuleras så att de kan följas på ett robotliknande sätt, det vill säga utan att behöva tänka... dock om instruktionerna [för att lösa kvadraten ekvation, hans exempel] ska följas av någon som vet hur man utför aritmetiska operationer men inte vet hur man extraherar en kvadratrot, då måste vi också tillhandahålla en uppsättning regler för att extrahera en kvadratrot för att uppfylla definitionen av algoritm" (s. 4-5)

Dessutom, "... inte alla instruktioner är acceptabla , eftersom de kan kräva att roboten har förmågor utöver de som vi anser vara rimliga ." Han ger exemplet med en robot som konfronteras med frågan är "Henry VIII en kung av England?" och att skriva ut 1 om ja och 0 om nej, men roboten har inte tidigare försetts med denna information. Och värre, om roboten tillfrågas om Aristoteles var en kung av England och roboten bara hade försetts med fem namn, skulle inte veta hur jag skulle svara. Alltså:

"en intuitiv definition av en acceptabel sekvens av instruktioner är en där varje instruktion är exakt definierad så att roboten garanterat kan lyda den" ( s. 6)

Efter att ha försett oss med sin definition, introducerar Stone Turing-maskinmodellen och konstaterar att den uppsättning av fem-tuplar som är maskinens instruktioner är "en algoritm ... känd som ett Turing-maskinprogram" (s. 9). Omedelbart därefter fortsätter han att säga att en " beräkning av en Turing-maskin beskrivs genom att säga:

"1. Bandalfabetet
. "2. Formen i vilken [input] parametrarna presenteras på bandet
"3. Turingmaskinens initiala tillstånd "
4
) Formen i vilken svaren [utdata] kommer att representeras på bandet när Turing-maskinen stannar
"5. Maskinprogrammet" (kursiv stil, s. 10

Denna exakta föreskrift av vad som krävs för "en beräkning" är i andan av vad som kommer att följa i Blass och Gurevichs arbete.

1995 Soares karaktärisering

"En beräkning är en process där vi går från initialt givna objekt, kallade ingångar , enligt en fast uppsättning regler, kallad ett program, procedur eller algoritm , genom en serie steg och kommer till slutet av dessa steg med en slutlig resultat, kallat output . Algoritmen , som en uppsättning regler som går från input till output, måste vara exakt och bestämd med varje successivt steg klart bestämt. Begreppet beräkningsbarhet avser de objekt som kan specificeras i princip genom beräkningar ... "(kursiv stil i original, fetstil tillagd s. 3)

2000 Berlinskis karaktärisering

Medan han studerade i Princeton i mitten av 1960-talet, var David Berlinski elev i Alonzo Church (jfr s. 160). Hans bok från år 2000 The Advent of the Algorithm: The 300-year Journey from an Idea to the Computer innehåller följande definition av algoritm :

" I logikerns röst:
" en algoritm är
en ändlig procedur,
skriven i en fast symbolisk vokabulär,
styrd av exakta instruktioner,
som rör sig i diskreta steg, 1, 2, 3, . . .,
vars utförande inte kräver någon insikt, smarthet,
intuition, intelligens eller skarpsyn,
och som förr eller senare tar slut. " (fetstil och kursiv stil i originalet, s. xviii)

2000, 2002 Gurevichs karaktärisering

En noggrann läsning av Gurevich 2000 får en att dra slutsatsen (draga slutsatsen?) att han tror att "en algoritm" faktiskt är "en Turing-maskin" eller "en pekmaskin" som gör en beräkning . En "algoritm" är inte bara symboltabellen som styr maskinens beteende, det är inte heller bara en instans av en maskin som gör en beräkning givet en viss uppsättning indataparametrar, och det är inte heller en lämpligt programmerad maskin med strömmen avstängd ; snarare är en algoritm maskinen som faktiskt gör alla beräkningar som den är kapabel till . Gurevich kommer inte direkt ut och säger detta, så som det formulerades ovan är denna slutsats (slutledning?) verkligen öppen för debatt:

". . . varje algoritm kan simuleras av en Turing-maskin ... ett program kan simuleras och därför ges en exakt betydelse av en Turing-maskin." (s. 1)
" Man tror ofta att problemet med att formalisera begreppet sekventiell algoritm löstes av Church [1936] och Turing [1936]. Till exempel, enligt Savage [1987], är en algoritm en beräkningsprocess definierad av en Turing-maskin. Church och Turing löste inte problemet med att formalisera begreppet sekventiell algoritm. Istället gav de (olika men likvärdiga) formaliseringar av begreppet beräkningsbar funktion, och det finns mer i en algoritm än funktionen den beräknar. (kursiv stil s. 3)
"Naturligtvis är begreppen algoritm och beräkningsbar funktion intimt relaterade: per definition är en beräkningsbar funktion en funktion som kan beräknas av en algoritm. . . . (sid. 4)


I Blass och Gurevich 2002 åberopar författarna en dialog mellan "Quisani" ("Q") och "Authors" (A), med Yiannis Moshovakis som en folie, där de kommer direkt ut och säger rakt ut:

" S: För att lokalisera oenigheten, låt oss först nämna två punkter av överensstämmelse. För det första finns det några saker som uppenbarligen är algoritmer enligt någons definition - Turing-maskiner, sekventiell-tids-ASM [Abstract State Machines] och liknande. . . För det andra, i den andra ytterligheten finns specifikationer som inte skulle betraktas som algoritmer enligt någons definition, eftersom de inte ger någon indikation på hur man beräknar någonting... Frågan är hur detaljerad informationen måste vara för att räknas som en algoritm ... Moshovakis tillåter vissa saker som vi bara skulle kalla deklarativa specifikationer, och han skulle förmodligen använda ordet "implementering" för saker som vi kallar algoritmer." (stycken sammanfogade för att underlätta läsbarheten, 2002:22)

Denna användning av ordet "implementering" skär rakt in i kärnan av frågan. Tidigt i tidningen säger Q sin läsning av Moshovakis:

"...[H]e skulle förmodligen tro att ditt praktiska arbete [Gurevich arbetar för Microsoft] tvingar dig att tänka på implementeringar mer än på algoritmer. Han är ganska villig att identifiera implementeringar med maskiner, men han säger att algoritmer är något mer allmänt. Vad det handlar om är att du säger att en algoritm är en maskin och Moschovakis säger att den inte är det." (2002:3)

Men författarna svamlar här och säger "[L]vi håller oss till "algoritm" och "maskin", och läsaren blir återigen förvirrad. Vi måste vänta till Dershowitz och Gurevich 2007 för att få följande fotnotkommentar:

". . . Ändå, om man accepterar Moshovakis synvinkel, så är det "implementeringen" av algoritmer som vi har bestämt oss för att karakterisera." (jfr fotnot 9 2007:6)

2003 Blass och Gurevichs karaktärisering

Blass och Gurevich beskriver deras arbete som utvecklat från övervägande av Turing-maskiner och pekarmaskiner , specifikt Kolmogorov-Uspensky-maskiner (KU-maskiner), Schönhage Storage Modification Machines (SMM) och länkautomater enligt Knuths definition. Gandys och Markovs arbete beskrivs också som inflytelserika föregångare.

Gurevich erbjuder en "stark" definition av en algoritm (fetstilad):

"...Turings informella argument till förmån för hans avhandling motiverar en starkare tes: varje algoritm kan simuleras av en Turing-maskin .... I praktiken skulle det vara löjligt...[Ändå] [kan] man generalisera Turingmaskiner så att vilken algoritm som helst, oavsett hur abstrakt, kan modelleras av en generaliserad maskin?...Men anta att sådana generaliserade Turingmaskiner existerar. Vad skulle deras tillstånd vara?...en första ordningens struktur ...en speciell liten instruktionsuppsättning räcker i alla fall ... beräkning som en utveckling av tillståndet ... kan vara icke-deterministisk ... kan interagera med sin miljö ... [kan vara] parallell och multi-agent ... [kunde ha] dynamisk semantik ... [de två grunderna för deras arbete är:] Turings avhandling ...[och] föreställningen om (första ordningens) struktur av [Tarski 1933]" (Gurevich 2000, s. 1-2)

Ovanstående frasberäkning som en utveckling av staten skiljer sig markant från definitionen av Knuth och Stone - "algoritmen" som ett Turing-maskinprogram. Snarare motsvarar det vad Turing kallade den fullständiga konfigurationen (jfr Turings definition i Undecidable, s. 118) -- och inkluderar både den aktuella instruktionen (tillståndet) och bandets status. [jfr Kleene (1952) sid. 375 där han visar ett exempel på ett band med 6 symboler på — alla andra rutor är tomma — och hur man Gödelize dess kombinerade tabell-band status].

I algoritmexemplen ser vi utvecklingen av staten från första hand.

1995 – Daniel Dennett: evolution som en algoritmisk process

Filosofen Daniel Dennett analyserar betydelsen av evolution som en algoritmisk process i sin bok Darwin's Dangerous Idea från 1995 . Dennett identifierar tre nyckelfunktioner i en algoritm:

  • Substratneutralitet : en algoritm förlitar sig på sin logiska struktur. Den speciella formen i vilken en algoritm manifesteras är alltså inte viktig (Dennetts exempel är long division: den fungerar lika bra på papper, på pergament, på en datorskärm eller med neonljus eller i skywriting). (sid. 51)
  • Underliggande sinneslöshet : oavsett hur komplicerad slutprodukten av den algoritmiska processen kan vara, är varje steg i algoritmen tillräckligt enkelt för att utföras av en icke-kännande, mekanisk enhet. Algoritmen kräver ingen "hjärna" för att underhålla eller använda den. "Standardläroboksanalogin konstaterar att algoritmer är recept av olika slag, designade för att följas av nybörjare kockar." (sid. 51)
  • Garanterat resultat : Om algoritmen exekveras korrekt kommer den alltid att ge samma resultat. "En algoritm är ett idiotsäkert recept." (sid. 51)

Det är på basis av denna analys som Dennett drar slutsatsen att "enligt Darwin är evolution en algoritmisk process". (sid. 60).

Men på föregående sida har han gått ut på en mycket längre lem. [ enligt vem? ] I samband med sitt kapitel med titeln "Processer som algoritmer", säger han:

"Men då ... finns det några gränser överhuvudtaget för vad som kan anses vara en algoritmisk process? Jag antar att svaret är NEJ; om du vill kan du behandla vilken process som helst på abstrakt nivå som en algoritmisk process ... Om vad slår dig som förbryllande är enhetligheten hos [havets] sandkorn eller styrkan hos det [härdade stål]-bladet, är en algoritmisk förklaring vad som kommer att tillfredsställa din nyfikenhet - och det kommer att vara sanningen... "
Oavsett hur imponerande produkterna av en algoritm, den underliggande processen alltid består av ingenting annat än en uppsättning individuella [ sic ] tanklösa steg som avlöser varandra utan hjälp av någon intelligent övervakning; de är 'automatiska' per definition: hur en automat fungerar." (s. 59)

Det är oklart från ovanstående om Dennett påstår att den fysiska världen i sig själv och utan observatörer är i sig algoritmisk (beräkningsmässig) eller om en symbolbehandlande observatör är det som tillför "mening" till observationerna.

2002 John Searle lägger till en klargörande varning till Dennetts karaktärisering

Daniel Dennett är en förespråkare för stark artificiell intelligens : idén att den logiska strukturen hos en algoritm är tillräcklig för att förklara sinnet . John Searle , skaparen av det kinesiska rummets tankeexperiment, hävdar att " syntax [det vill säga logisk struktur] i sig inte är tillräcklig för semantiskt innehåll [det vill säga mening]" ( Searle 2002 , s. 16). Med andra ord, "betydelsen" av symboler är relativ till det sinne som använder dem; en algoritm – en logisk konstruktion – i sig är otillräcklig för ett sinne.

Searle varnar dem som hävdar att algoritmiska (beräknings)processer är naturliga (till exempel kosmologer, fysiker, kemister, etc.):

Beräkning [...] är observatörsrelativ, och detta beror på att beräkning definieras i termer av symbolmanipulation, men begreppet "symbol" är inte ett begrepp om fysik eller kemi. Något är en symbol endast om det används, behandlas eller betraktas som en symbol. Det kinesiska rumsargumentet visade att semantik inte är en inneboende syntax. Men vad detta visar är att syntax inte är en naturlig del av fysiken. [...] Något är en symbol endast i förhållande till någon observatör, användare eller agent som tilldelar det en symbolisk tolkning [...] du kan tilldela en beräkningstolkning till vad som helst. Men om frågan ställs: "Är medvetandet i sig beräkningsmässigt?" svaret är: ingenting är i sig beräkningsmässigt [kursiv stil för att betona]. Beräkning existerar endast i förhållande till någon agent eller observatör som påtvingar en beräkningstolkning av något fenomen. Detta är en uppenbar poäng. Jag skulle ha sett den för tio år sedan men det gjorde jag inte.

— John Searle, Searle 2002 , sid. 17

2002: Boolos-Burgess-Jeffrey-specifikation av Turing-maskinberäkning

För exempel på denna specifikationsmetod applicerad på additionsalgoritmen "m+n" se Algoritmexempel.

Ett exempel i Boolos-Burgess-Jeffrey (2002) (s. 31–32) visar den precision som krävs i en fullständig specifikation av en algoritm, i det här fallet att lägga till två tal: m+n. Det liknar stenkraven ovan.

(i) De har diskuterat rollen av "talformat" i beräkningen och valt "tally notation" för att representera tal:

"Visst kan beräkning vara svårare i praktiken med vissa notationer än andra... Men... det är i princip möjligt att göra i vilken annan notation som helst, helt enkelt genom att översätta data... I syfte att skapa en noggrant definierad uppfattning om beräkningsbarhet , det är bekvämt att använda monadisk eller tally notation" (s. 25-26)

(ii) I början av deras exempel specificerar de maskinen som ska användas i beräkningen som en Turing-maskin . De har tidigare specificerat (sid. 26) att Turing-maskinen kommer att vara av 4-tupel, snarare än 5-tupel. För mer om denna konvention se Turing-maskinen .

(iii) Tidigare har författarna specificerat att bandhuvudets position kommer att indikeras med en nedsänkt text till höger om den skannade symbolen. För mer om denna konvention se Turing-maskinen . (I det följande läggs fetstil till för att betona):

"Vi har inte gett en officiell definition av vad det är för en numerisk funktion att vara beräkningsbar av en Turing-maskin , som specificerar hur indata eller argument ska representeras på maskinen, och hur utdata eller värden representeras. Våra specifikationer för en k- platsfunktion från positiva heltal till positiva heltal är följande:
"(a) [ Initialt talformat: ] Argumenten m 1 , ... m k , ... kommer att representeras i monadisk [unär] notation av block av dessa siffror av slag, varje block separerat från nästa av ett enda ämne, på en annars blank tejp.
Exempel: 3+2, 111B11
"(b) [ Initial head location, initial state: ] Inledningsvis kommer maskinen att skanna den 1:an längst till vänster på bandet och kommer att vara i sitt initiala läge, läge 1.
Exempel: 3+2 , 1 1 111B11
"(c) [ Lyckad beräkning -- talformat vid stopp: ] Om funktionen som ska beräknas tilldelar ett värde n till argumenten som representeras initialt på bandet, kommer maskinen så småningom att stanna på ett band som innehåller ett block med streck, och annars tomt...
Exempel: 3+2, 11111
"(d) [ Lyckad beräkning -- huvudets placering vid stopp: ] I det här fallet [c] kommer maskinen att sluta skanna den 1:an längst till vänster på bandet...
Exempel: 3+2, 1 n 1111
"(e) [ Misslyckad beräkning -- misslyckande att stoppa eller stoppa med icke-standardiserat talformat: ] Om funktionen som ska beräknas inte tilldelar argumenten något värde som visas initialt på bandet, då kommer maskinen antingen aldrig att stanna, eller kommer den att stanna i någon icke-standardkonfiguration..."(ibid)
Exempel: B n 11111 eller B11 n 111 eller B11111 n

Denna specifikation är ofullständig: den kräver platsen för var instruktionerna ska placeras och deras format i maskinen--

(iv) i den finita tillståndsmaskinens TABELL eller, i fallet med en Universal Turing-maskin på bandet, och
(v) tabellen med instruktioner i ett specificerat format

Denna senare punkt är viktig. Boolos-Burgess-Jeffrey ger en demonstration (s. 36) att förutsägbarheten av posterna i tabellen gör att man kan "krympa" tabellen genom att sätta posterna i ordning och utelämna inmatningstillståndet och symbolen. Faktum är att exemplet med Turing-maskinberäkningen bara krävde de fyra kolumnerna som visas i tabellen nedan (men notera: dessa presenterades för maskinen i rader ):

Ange qk
Skannad symbol
Handling
Nästa tillstånd qk
Ange qn
Skannad symbol
Handling
Nästa tillstånd qk
Ange qk
B-aktion
B-nästa tillstånd qkB
1-åtgärd
1: nästa tillstånd qk1
1 B R H 1 1 R 2 1 R H R 2
2 B P 3 2 1 R 2 2 P 3 R 2
3 B L 4 3 1 R 3 3 L 4 R 3
4 B L 5 4 1 E 4 4 L 5 E 4
5 B R H 5 1 L 5 5 R H L 5

2006: Sipsers påstående och hans tre beskrivningsnivåer

För exempel på denna specifikationsmetod applicerad på additionsalgoritmen "m+n" se Algoritmexempel.

Sipser börjar med att definiera "algoritm" enligt följande:

"Informellt sett är en algoritm en samling enkla instruktioner för att utföra en uppgift. Vanligt i vardagen kallas algoritmer ibland för procedurer eller recept (kursivt i original, s. 154) "
...vårt verkliga fokus från och med nu är på algoritmer. Det vill säga, Turing-maskinen fungerar bara som en exakt modell för definitionen av algoritm .... vi behöver bara vara tillräckligt bekväma med Turing-maskiner för att tro att de fångar alla algoritmer" (s. 156)

Menar Sipser att "algoritm" bara är "instruktioner" för en Turing-maskin, eller är kombinationen av "instruktioner + en (specifik variant av) Turing-maskin"? Till exempel definierar han de två standardvarianterna (multi-band och icke-deterministisk) av sin speciella variant (inte samma som Turings original) och fortsätter, i sina Problem (sidorna 160-161), att beskriva ytterligare fyra varianter ( skriv en gång, dubbelt oändligt band (dvs vänster- och höger-oändligt), vänsteråterställning och "håll kvar istället för vänster). Dessutom ställer han vissa begränsningar. Först måste inmatningen kodas som en sträng (s. 157) och säger om numeriska kodningar i samband med komplexitetsteori:

"Men observera att unär notation för kodning av tal (som i siffran 17 som kodas av det enariska numret 11111111111111111) inte är rimlig eftersom den är exponentiellt större än verkligt rimliga kodningar, som bas-k-notation för valfri k ≥ 2. " (sid. 259)

Van Emde Boas kommenterar ett liknande problem med avseende på den abstrakta beräkningsmodellen för random-access machine (RAM) som ibland används i stället för Turing-maskinen när man gör "analys av algoritmer": "Frånvaron eller närvaron av multiplikativ och parallell bitmanipulation operationer är av relevans för en korrekt förståelse av vissa resultat i analysen av algoritmer.

"... [T] här existerar knappast något som en "oskyldig" förlängning av standard RAM-modellen i de enhetliga tidsmåtten; antingen har man bara additiv aritmetik eller så kan man lika gärna inkludera alla rimliga multiplikativa och/eller bitvisa Booleska instruktioner om små operander." (Van Emde Boas, 1990:26)

När det gäller ett "beskrivningsspråk" för algoritmer avslutar Sipser jobbet som Stone och Boolos-Burgess-Jeffrey påbörjade (fetstil tillagd). Han erbjuder oss tre nivåer av beskrivning av Turing-maskinalgoritmer (s. 157):

Beskrivning på hög nivå : "där vi använder ... prosa för att beskriva en algoritm, och ignorerar implementeringsdetaljerna. På den här nivån behöver vi inte nämna hur maskinen hanterar sitt band eller huvud."
Implementeringsbeskrivning : "där vi använder ... prosa för att beskriva hur Turing-maskinen rör på huvudet och hur den lagrar data på bandet. På den här nivån ger vi inga detaljer om tillstånd eller övergångsfunktion."
Formell beskrivning : "... den lägsta, mest detaljerade, beskrivningsnivån... som i sin helhet redogör för Turing-maskinens tillstånd, övergångsfunktion, och så vidare."

2011: Yanofsky

I Yanofsky (2011) definieras en algoritm som den uppsättning program som implementerar den algoritmen: uppsättningen av alla program är uppdelad i ekvivalensklasser. Även om uppsättningen av program inte bildar en kategori, bildar uppsättningen av algoritmer en kategori med extra struktur. Villkoren som beskriver när två program är likvärdiga visar sig vara koherensrelationer som ger den extra strukturen till kategorin algoritmer.

Anteckningar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Algorithm_characterizations&oldid=1107118075 "