Laskettava toiminto

Computable toiminto (tai rekursiivinen toiminto ) on puoliksi laskettava funktio (tai rekursiivinen osittainen funktio ), joka on myös yhteensä , eli joka on määritelty koko sen domeenin. Nämä ovat toiminnot, jotka laskee "päättävä" Turing-kone .

Laskettava funktio ei välttämättä ole "fyysisesti laskettavissa", esimerkiksi jos sen toteutusaika ylittää useita miljardeja vuosia.

Yksinkertaisimmat esimerkit laskettavista funktioista ovat vakiofunktiot . Poissuljetun kolmanneksen periaatteen seurauksena on, että vakiofunktio, joka kokonaislukuun yhdistää 1, jos Goldbach-oletus on totta, ja 0, jos se on väärä, on laskettavissa, vaikka emme tiedä tänään, onko oletus totta. Tämä osoittaa, kuinka tämän periaatteen soveltaminen tuhoaa intuitiivisen käsityksen laskettavuudesta.

Esimerkkejä

• Tietokoneohjelmat, jotka pysähtyvät (suoritettaessa mitä tahansa syötettä), ovat laskettavia toimintoja.

• Funktio, joka ottaa tulona Turingin koneen (jota edustaa kokonaisluku) ja tämän koneen syötteen ja yhdistää ne arvoon 1, jos tämä kone pysähtyy tälle tulolle, ei mitään muuta, on puoliksi laskettava toiminto. Ainoastaan poissuljetun kolmanneksen periaatteen soveltaminen mahdollistaa tämän toiminnon laajentamisen kokonaisfunktioksi, joka antaa 0, jos tarkasteltava kone ei pysähdy tarkasteltavaan tuloon, mutta tätä toimintoa ei tällöin voida laskea (lisätietoja on kohdassa artikkeli Sammutusongelma ).
• GCD: n laskeminen on laskettava toiminto.

Viitteet

1. Alain Prochiantz , kone-mieli , Odile Jacob,5. tammikuuta 2001( lue verkossa ).

Katso myös

• Kirkon opinnäytetyö
• Laskettavuus
• Päätettävyys