Laskettu funktio

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 10. huhtikuuta 2019 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Laskettavat funktiot  ovat joukko funktioita, jotka voidaan toteuttaa Turingin koneella . Funktion laskentatehtävää kutsutaan algoritmisesti ratkaistavaksi tai algoritmisesti ratkaisemattomaksi sen mukaan, onko tämän funktion laskeva algoritmi mahdollinen.

Joukkona pidetään yleensä  joukkoa - sanajoukkoa binääriaakkosissa sillä ehdolla, että laskennan tulos voi olla paitsi sana, myös erityinen arvo "epävarmuus", joka vastaa tapausta, jossa algoritmi "jumiutuu". Siten voidaan antaa seuraava määritelmä :

jossa , a  on erityinen elementti, joka ilmaisee epävarmuutta.

Joukon roolia voi esittää luonnollisten lukujen joukko, johon elementti lisätään , ja sitten laskettavat funktiot ovat joitain luonnollisen argumentin luonnollisten funktioiden osajoukkoa. On kätevää olettaa, että joukkona voivat toimia erilaiset laskettavat joukot - luonnollisten lukujen joukko, rationaalilukujen joukko, joidenkin äärellisten aakkosten sanajoukko jne. On tärkeää, että äärellisessä on jokin muodollinen kieli aakkoset joukon elementtien kuvaamiseen ja että oikea tunnistamisongelma laskettiin. Esimerkiksi luonnollisten lukujen kuvaamiseen on kätevää käyttää binäärilukujärjestelmää - kieltä aakkosten luonnollisten lukujen kuvaamiseen .

Tässä määritelmässä Turingin koneen suorittimen sijasta voidaan ottaa yksi Turingin-täydellisistä suorittajista. Karkeasti sanottuna "viitetoimija" voi olla jokin abstrakti tietokone, joka on samanlainen kuin käytetyt henkilökohtaiset tietokoneet, mutta jossa on mahdollisesti ääretön muisti ja arkkitehtoniset ominaisuudet, jotka mahdollistavat tämän äärettömän muistin käytön.

On tärkeää huomata, että tämän suorittimen ohjelmien joukko (esimerkiksi joukko Turingin koneita, joissa on kiinteä tulo- ja lähtödata aakkoset) on laskettavissa . Siksi laskettavien funktioiden joukko on korkeintaan laskettavissa, kun taas muodon funktioiden joukko on laskematon, jos se on laskettavissa. Tämä tarkoittaa, että on ei-laskettavia funktioita, ja niiden joukon kardinaliteetti on suurempi kuin laskettavien funktioiden joukon kardinaliteetti. Esimerkki ei-laskettavasta funktiosta (algoritmisesti ratkaisematon ongelma) voi olla pysäytystoiminto  - funktio, joka vastaanottaa jonkin Turingin koneen kuvauksen ja syötteen sille ja palauttaa 0 tai 1 riippuen siitä pysähtyykö kone annettu syöte vai ei. Toinen esimerkki ei-laskettavasta funktiosta on Kolmogorovin kompleksisuus .

Historia

Ymmärrys siitä, että jotkin lomakkeen toiminnot ovat laskettavissa ja jotkut eivät, ilmestyi jo ennen ensimmäisten tietokoneiden tuloa. Laskettavuuden teoria on peräisin Turingin väitöskirjasta ( 1936 ), jossa hän esitteli abstraktin tietokoneen käsitteen ja sillä laskettavissa olevat funktiot. Lasketettavuuden teorian kehittyessä muotoiltiin useita määritelmiä, jotka, kuten myöhemmin kävi ilmi, määrittelevät saman funktiojoukon - laskettavien funktioiden joukon:

Katso myös

Linkit