Churchin–Turingin teesi

Wikipedia
Ohjattu sivulta Church-Turing -teesi
Loikkaa: valikkoon, hakuun

Church–Turingin konjektuuri (myös Church-Turingin teesi, Churchin väite ja Turingin väite) on yhdistetty hypoteesi niiden funktioiden luonteesta, joiden arvot ovat tehokkaasti laskettavissa. Yksinkertaisimmin ilmaistuna se sanoo, että "kaikki laskettavissa oleva on laskettavissa Turingin koneella."

1900-luvun alkupuolella tehtiin useita yrityksiä formalisoida laskettavuuden käsitettä:

  • Yhdysvaltalainen matemaatikko Alonzo Church loi metodin funktoioiden määrittämiseen, jota kutsutaan lambda-kalkyyliksi:
  • Brittiläinen matemaatikko Alan Turing loi teoreettisen mallin koneelle, joka voisi suorittaa laskelmia syöttötiedoista.
  • Church yhdessä matemaatikko Stephen Kleenen ja loogikko J. B. Rosserin kanssa loivat virallisen määritelmän funktioille, joiden arvot voisivat olla laskettavissa rekursiolla.

Kolme matemaatikkoa, Emil Post, Alonzo Church ja Alan Turing, kehittivät 1936 toisistaan riippumatta ensimmäiset universaalien tietokoneiden abstraktit mallit.[1] Matemaatikko Roger Penrose esitti, että sitä sanottaisiin Turingin periaatteeksi.[2]

Turingin periaate Turingin ilmaisemassa muodossa[muokkaa | muokkaa wikitekstiä]

Jokainen funktio, jota pidetään laskettavana luonnollisella tavalla, voidaan laskea universaalilla Turingin koneella.[3]

Katso myös[muokkaa | muokkaa wikitekstiä]

Churchin–Turingin–Deutschin periaate

Viitteet[muokkaa | muokkaa wikitekstiä]

Tämä artikkeli tai sen osa on käännetty tai siihen on haettu tietoja vieraskielisen Wikipedian artikkelista.