Problemo de halto
Problemo de halto estas tasko de teorio de nombrigebleco, kiu povas esti neformale donita jene:
- Se vi konas fontkodon de programo kaj ties eniron, decidu, ĉu la programo haltos aŭ ĉu ĝi funkcios por ĉiam sen halto.
En la jaro 1936 Alan Turing pruvis, ke ĝenerala algoritmo, kiu solvus la problemon de halto por ĉiuj eniroj de ĉiuj programoj, ne ekzistas. La problemo de halto tial estas markata kiel algoritme nedecidebla problemo.
Skizo de la pruvo
La nedecideblecon de la problemo de halto eblas pruvi per disputo.
- Komenca supozo: Ni supozu, ke la problemon de halto eblas decidi. Tio signifas, ke ekzistas ia programo Haltu(programon, eniron), kiu estas universala solvo de la problemo de halto.
Tiu funkcias tiel, ke se la vokado programo(eniro) post fina kvanto de paŝoj finiĝos, poste ĝi Haltu(programon, eniron) revenigos la valoron JES, en mala kazo (se la vokado programo(eniro) encikliĝus) revenigos la valoron NE. - Ni konstruu programon Paradokso(x), kiu intence encikliĝos, se la vokado de programo Haltu(x x) revenigos JES, kaj ĝi haltos, se la vokado de programo Haltu(x x) revenigos NE.
- Nun ni demandu, kio estas la rezulto de la vokado Paradokso(Paradokso).
- Ni supozu por momento, ke Haltu(Paradokson, Paradokson) revenigas JES. Sed laŭ la difino de la programo Haltu validas, ke se Paradokso(Paradokso) encikliĝos, poste la Haltu(Paradokson, Paradokson) devas revenigi NE. Ni venis al disputo.
- Ni supozu aliflanke por momento, ke la Haltu(Paradokson, Paradokson) revenigas NE. El la difino de la programo Paradokso ni poste scias, ke la Paradokso(Paradokso) haltos. Sed laŭ la difino de la programo Haltu validas, ke se la Paradokso(Paradokso) haltos, poste la Haltu(Paradokson, Paradokson) devas revenigi JES. Denove ni venis al disputo.
- Ĉar ni elĉerpis ĉiujn eblecojn kaj ĉiam ni venis al disputo, la komenca supozo devas esti malvera. El tio rezultas, ke la programo Haltu(programon, eniron), tiel kiel ĝi estis difinita, ne ekzistas.
Vidu ankaŭ
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.