Daugiajuostės mašinos imitavimas ir modelių lygiavertiškumas
Fiksuotą deterministinę Tiuringo mašiną su baigtiniu juostų skaičiumi, veikiančią per laiką t(n)≥n, galima imituoti vienajuoste mašina per O(t(n)²) laiką, saugant juostų turinį bei galvučių žymeklius ir peržiūrint juos kiekviename imituojamame žingsnyje.
Esminės žinios
Fiksuotą deterministinę Tiuringo mašiną su baigtiniu juostų skaičiumi, veikiančią per laiką t(n)≥n, galima imituoti vienajuoste mašina per O(t(n)²) laiką, saugant juostų turinį bei galvučių žymeklius ir peržiūrint juos kiekviename imituojamame žingsnyje. Šių modelių sprendžiamų kalbų aibės ir polinominio laiko klasė sutampa.
Sąlygos ir taikymo ribos
- Tai konkrečiai apibrėžtas klasikinio mašinos modelio imitavimas, o ne įrodymas apie visus įmanomus fizinius skaičiavimus.
- Vienodas apskaičiuojamumas nereiškia vienodos vykdymo trukmės; negalima numanomai įtraukti apribotų sąnaudų aritmetinių operacijų su bet kokio dydžio skaičiais.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitos 12 skaidrės 23–25: mašinų su baigtiniu juostų skaičiumi ir vienajuosčių mašinų simuliavimas bei polinominės papildomos sąnaudos.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaitytas visas 241 glaustas teiginys, hipotezės, atskirai pateiktos lygtys ir susitarimai bei visos 596 iš šių įrašų išeinančios semantinės sąsajos; peržiūrėta visa autoriaus 241 įrašo tikslių šaltinių patikros matrica ir nurodyti ribotumai. Siekiant aprėpti visą rinkinį, perskaityti 105 ankstesni faktiškai perimti matematikos ir informacijos įrašai. Nepriklausomai tikslingai peržiūrėti pirminių šaltinių skyriai išvardyti toliau; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atliekama informacinio turinio peržiūra, o ne žmogaus specialisto patvirtinimas, išsamus vadovėlio atkūrimas ar eksperimentinis atkartojimas. Peržiūros patvirtinimas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-turing-model-equivalence
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra