eo eo eo pt eo eo eo eo eo eo eo eo eo eo eo eo eo eo eo eo eo eo eu lt eo eo eo eo de es eo eo eo eo eo sv ur eo eo eo eo es eo eo eo eo eo eo eo eo tr fi eo eo it eo eo eo eo eo eo eo eo eo eo ar bg ca hbs_lat da de el en es fa fi fr he hi hbs_lat it ja ko nl pl pt ru en sk hbs_lat sv th tr fy vi zh eo eo eo eo eo eo eo eo eo
Problemo de halto - Vikipedio
El Vikipedio, la libera enciklopedio
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[redakti | redakti fonton]
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ŭ[redakti | redakti fonton]
Teoremoj de Gödel pri nekompleteco
Informoj pri la paĝo
Citi ĉi tiun artikolon
Ĉi tiu paĝo estis lastafoje redaktita je 04:08, 8 jun. 2014.
La teksto disponeblas laŭ la permesilo Krea Komunaĵo Atribuite-Samkondiĉe 3.0 Neadaptita; eble aldonaj kondiĉoj aplikeblas. Vidu la uzkondiĉojn por detaloj.
Regularo pri respekto de la privateco
Vidigo por porteblaj aparatoj