Beräknad funktion

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 april 2019; verifiering kräver 1 redigering .

Beräknarbara funktioner  är den uppsättning funktioner av formuläret som kan implementeras på en Turing-maskin . Uppgiften att beräkna en funktion kallas algoritmiskt beslutbar eller algoritmiskt obestämbar , beroende på om algoritmen som beräknar denna funktion är möjlig.

Som en mängd betraktas vanligtvis en mängd  - en uppsättning ord i det binära alfabetet , med förbehållet att resultatet av beräkningen inte bara kan vara ett ord, utan också ett speciellt värde "osäkerhet", motsvarande fallet när algoritmen "hänger sig". Således kan följande definition ges :

där , a  är ett speciellt element som anger osäkerhet.

Rollen för en mängd kan spelas av mängden naturliga tal, till vilken elementet läggs , och sedan är de beräkningsbara funktionerna någon delmängd av naturligt värderade funktioner i det naturliga argumentet. Det är bekvämt att anta att olika räknebara mängder kan fungera som mängden - mängden naturliga tal, mängden rationella tal, mängden ord i något finita alfabet etc. Det är viktigt att det finns något formellt språk i det finita alfabetet för att beskriva elementen i uppsättningen och att problemet med att känna igen rätt beräknades. Till exempel, för att beskriva naturliga tal, är det bekvämt att använda det binära talsystemet - språket för att beskriva naturliga tal i alfabetet .

I den här definitionen, istället för en Turing-maskinexekutor, kan en av de Turing-kompletta exekutorerna tas. Grovt sett kan "referensexekutorn" vara någon abstrakt dator, liknande de persondatorer som används, men med potentiellt oändligt minne och arkitektoniska egenskaper som tillåter användningen av detta oändliga minne.

Det är viktigt att notera att uppsättningen av program för denna executor (till exempel uppsättningen Turing-maskiner med ett fast alfabet av in- och utdata) är räknebar . Därför är uppsättningen av beräkningsbara funktioner som mest räknebar, medan uppsättningen funktioner i formuläret är oräknelig, om den är räknbar. Detta betyder att det finns icke-beräknbara funktioner, och kardinaliteten för deras uppsättning är större än kardinaliteten för uppsättningen av beräkningsbara funktioner. Ett exempel på en icke beräkningsbar funktion (algoritmiskt olösligt problem) kan vara en stoppdetekteringsfunktion  - en funktion som får en beskrivning av någon Turing-maskin och en ingång för den som ingång, och returnerar 0 eller 1 beroende på om denna maskin stannar vid en given ingång eller inte. Ett annat exempel på en icke-beräknbar funktion är Kolmogorov-komplexiteten .

Historik

Insikten om att vissa funktioner i formuläret är beräkningsbara, och andra inte, dök upp redan innan de första datorernas tillkomst. Teorin om beräkningsbarhet härstammar från Turings avhandling ( 1936 ), där han introducerade begreppet en abstrakt dator och funktioner som är beräkningsbara på den. När teorin om beräkningsbarhet utvecklades formulerades flera definitioner, som, som det visade sig senare, definierar samma uppsättning funktioner - uppsättningen av beräkningsbara funktioner:

Se även

Länkar