Problemo de halto
problemo, ne algoritme solvebla, de ĉu iu donita programo haltos aŭ ruliĝos senfine / From Wikipedia, the free encyclopedia
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.