Beregnet funktion

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

Beregnerbare funktioner  er det sæt funktioner i formen , der kan implementeres på en Turing-maskine . Opgaven med at beregne en funktion kaldes algoritmisk afgørbar eller algoritmisk ubeslutsom , afhængig af om algoritmen , der beregner denne funktion, er mulig.

Som et sæt betragtes som regel  et sæt - et sæt af ord i det binære alfabet , med det forbehold, at resultatet af beregningen ikke kun kan være et ord, men også en særlig værdi "usikkerhed", svarende til det tilfælde, hvor algoritmen "hænger". Således kan følgende definition gives :

hvor , a  er et særligt element, der angiver usikkerhed.

Et sæts rolle kan spilles af sættet af naturlige tal, hvortil elementet er tilføjet , og så er de beregnelige funktioner en delmængde af naturligt værdifulde funktioner i det naturlige argument. Det er praktisk at antage, at forskellige tællelige mængder kan fungere som mængden - mængden af ​​naturlige tal, mængden af ​​rationelle tal, mængden af ​​ord i et eller andet endeligt alfabet osv. Det er vigtigt, at der er noget formelt sprog i det endelige. alfabet til at beskrive elementerne i sættet , og at problemet med at genkende korrekt blev beregnet. For at beskrive naturlige tal er det for eksempel praktisk at bruge det binære talsystem - sproget til at beskrive naturlige tal i alfabetet .

I denne definition, i stedet for en Turing-maskine-eksekutor, kan en af ​​de Turing-komplette eksekvere tages. Groft sagt kan "referenceudføreren" være en eller anden abstrakt computer, der ligner de anvendte personlige computere, men med potentielt uendelig hukommelse og arkitektoniske funktioner, der tillader brugen af ​​denne uendelige hukommelse.

Det er vigtigt at bemærke, at sættet af programmer for denne executor (for eksempel sættet af Turing-maskiner med et fast alfabet af input- og outputdata) kan tælles . Derfor er sættet af beregnelige funktioner højst tælleligt, mens sættet af funktioner i formularen er utælleligt, hvis det kan tælles. Det betyder, at der er ikke-beregnbare funktioner, og kardinaliteten af ​​deres sæt er større end kardinaliteten af ​​sættet af beregnelige funktioner. Et eksempel på en ikke-beregnerbar funktion (algoritmisk uløseligt problem) kan være en stopdetektionsfunktion  - en funktion, der modtager en beskrivelse af en eller anden Turing-maskine og et input til den som input, og returnerer 0 eller 1 afhængig af om denne maskine stopper kl. et givet input eller ej. Et andet eksempel på en ikke-beregnerbar funktion er Kolmogorov-kompleksiteten .

Historie

Forståelsen af, at nogle funktioner i formularen er beregnelige, og nogle ikke er, dukkede op allerede før fremkomsten af ​​de første computere. Teorien om computability stammer fra Turings afhandling ( 1936 ), hvori han introducerede begrebet en abstrakt computer og funktioner, der kan beregnes på den. Efterhånden som teorien om beregningsevne udviklede sig , blev der formuleret flere definitioner, som, som det viste sig senere, definerer det samme sæt funktioner - sættet af beregnelige funktioner:

Se også

Links