Sustojimo problemos neišsprendžiamumas
Bendrajame skaičiavimo modelyje nėra visur apibrėžto algoritmo, kuris nustatytų, ar programa sustos, kiekvienai programai ir įvesčiai.
Esminės žinios
Nėra algoritmo, kuris visada baigtų darbą ir kiekvienai programos bei įvesties porai Tiuringo pilname skaičiavimo modelyje teisingai nustatytų, ar ta programa galiausiai sustos su ta įvestimi.
Sąlygos ir taikymo ribos
- Teorema taikoma neribojamoms programoms bendrajame modelyje, kuriame potencialiai prieinama atmintis ir veikimo laikas nėra apriboti.
- Ji neatmeta galimybės nustatyti konkrečių programų ar ribotų jų klasių sustojimą, taip pat tikrinti vykdymą neviršijant nustatytos išteklių ribos.
Šaltiniai · 4
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Bendroji neišsprendžiamumo teorema ir diagonalinis argumentas.
2026-10-10 · Formali registrinės mašinos formuluotė palyginta su nepriklausomu programos lygmens argumentu; apie visas ribotas kalbas neteigiama.
Pagrindinių žinių peržiūra
2026-10-10 · Fresh primary-source inspection of the complete compact record, including every statement, equation, quantity and material condition, followed by independent AI editorial review. This check does not certify all linked lessons or every passage of every cited publication.
Šaltiniai iš kitų vietų
Sutampa nurodytose ribose
No general algorithm decides halting for every program/input pair.
The program model incorporates inputs as natural numbers; bounded or restricted cases are outside the theorem.
University of Auckland, Department of Computer Science
- Lectures on Philosophy and Computation New Zealandanglų
Slides 4–6 (PDF pp.4–6)
- Lectures on Philosophy and Computation
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-halting-problem
- Versija
- core.1
- Struktūruotas žinyno įrašas
- Esminiai pagrindai · pirmasis rinkinys