Tiuringo mašinos ir efektyvusis skaičiavimas
Baigtinis instrukcijų rinkinys gali valdyti veiksmus neribotoje įrašomojoje juostoje.
Esminės žinios
Tiuringo mašina naudoja baigtinį būsenų rinkinį ir perėjimo taisykles, kad skaitytų, rašytų ir judėtų juostoje. Universalioji mašina imituoja užkoduotas mašinas. Čerčo–Tiuringo tezė sutapatina efektyviai apskaičiuojamas procedūras su Tiuringo mašina apskaičiuojamomis procedūromis.
Sąlygos ir taikymo ribos
- Neribota juosta yra matematinė abstrakcija; sustojantis skaičiavimas atliekamas per baigtinį žingsnių skaičių.
- Ši tezė apibūdina efektyviąją procedūrą, o ne teigia teoremą, kad kiekvienas fizinis procesas ar uždavinys yra apskaičiuojamas.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Skyriai 2–4: baigtinis valdymo įtaisas, įrašomoji juosta, universalumas ir Čerčo–Tiuringo tezė; išsaugota tikrojo 2008 m. PDF dokumento autorystė.
2026-10-10 · Mašinos modelis, universalumas ir tezė su apibrėžta taikymo sritimi; nesusiję istoriniai pavyzdžiai neįtraukti.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-turing-machines
- Versija
- university-reference.1
- Struktūruotas žinyno įrašas
- Universitetinis žinynas