Apskaičiuojamoji savinuoroda ir rekursijos teorema
Bet kuriai Tiuringo mašinai T, gaunančiai mašinos aprašą ir įprastą įvestį, galima sudaryti mašiną R, kuri su įvestimi x elgiasi taip, kaip T su (⟨R⟩,x).
Esminės žinios
Bet kuriai Tiuringo mašinai T, gaunančiai mašinos aprašą ir įprastą įvestį, galima sudaryti mašiną R, kuri su įvestimi x elgiasi taip, kaip T su (⟨R⟩,x). Vadinasi, kiekviena visur apibrėžta apskaičiuojamoji transformacija F, atvaizduojanti galiojančius mašinų aprašus į galiojančius aprašus, turi semantinį nejudamąjį tašką R, kuriam L(R)=L(F(⟨R⟩)).
Sąlygos ir taikymo ribos
- Naudojamas standartinis efektyvus mašinų kodavimas, leidžiantis apskaičiuojamai konstruoti mašinas, pateikti jų aprašus kaip duomenis ir atlikti universaliąją simuliaciją; pati T gali nesustoti.
- Nejudamasis taškas susijęs su elgsena arba atpažįstama kalba, o ne su pirminio teksto lygybe, efektyvumu ar neapskaičiuojamąja transformacija. Tai, kad F yra visur apibrėžta, užtikrina, jog galima gauti galiojančią transformuotą mašiną.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitos 11 skaidrėse 4 ir 6 – mašinos aprašo konstravimas ir rekursijos teorema; skaidrėje 8 – nejudamojo taško teorema ir įrodymas simuliacijos būdu. Įvesties poros elementų tvarka yra aiškiai nurodytas lygiavertis kodavimo susitarimas.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi glaustai suformuluoti teiginiai (241), hipotezės, pateiktos lygtys ir susitarimai bei visos kilmės semantinės sąsajos (596); peržiūrėta visa autoriaus sudaryta 241 įrašo tikslių šaltinių patikros matrica ir deklaruoti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai ir nepriklausomai peržiūrėti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atlikta informacinio turinio peržiūra, o ne žmogaus eksperto patvirtinimas atitinkamoje mokslo srityje, išsamus vadovėlio atkūrimas ar eksperimentinis pakartojimas. Peržiūros įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-computable-recursion-theorem
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra