Vikipedio:Projekto matematiko/Problemo de haltado

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al Problemo de haltado (eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

En komputebleca teorio la problemo de haltado estas decida problemo kiu povas esti neformale komencita kiel sekvas:

Donita priskribo de programo kaj ĝia komenca (enigo, enigi), difini ĉu la programo, kiam ekzekutis sur ĉi tiu (enigo, enigi), iam (digas, endigigas, haltas) ((kompletigas, plenumas)). La alternativo estas (tiu, ke, kiu) ĝi (kuras, rulas) eterne sen haltanta.

Alan Turing (pruvita, pruvis) en 1936 (tiu, ke, kiu) ĝenerala algoritmo al solvi la problemo de haltado por ĉiuj ebla (enigoj, enigas) ne povas ekzisti. Ni diri (tiu, ke, kiu) la problemo de haltado estas nedecidebla super Turingaj aŭtomatoj. ([1] kun respekto al _attribution_ de "problemo de haltado" al Turing-a.)

Enhavo 1 Formala (propozicio, frazo, ordono) 2 Graveco kaj konsekvencoj 3 Skizi de pruvo 4 Komuna _pitfalls_ 5 Formaligo de la problemo de haltado 6 Interrilato kun Teoremoj de nekompleteco 7 Povas (homoj, homas) solvi la problemo de haltado? 8 Agnoskantaj partaj solvaĵoj 9 Historio de la problemo de haltado 10 Piednotoj 11 Referencoj

[redaktu] Formala (propozicio, frazo, ordono)

Unu ebla vojo de formale (ŝtatanta, statanta) la problemo de haltado estas kiel sekvas:

Donita Godela numerado de la komputeblaj funkcioj,

kun la Cantor-a paranta funkcio,

la aro estas (nomita, vokis) la haltanta aro.

La problemo de decidanta ĉu la haltanta aro estas rekursie ĉu ne estas (nomita, vokis) la problemo de haltado. Kiel la aro estas rekursie numerigebla la problemo de haltado estas ne solvebla per komputebla funkcio.

Alternativa ekvivalento (formulaĵoj, formulaĵas), ekzemple eksplicite uzantaj Turingaj aŭtomatoj, estas ebla.

[redaktu] Graveco kaj konsekvencoj

La historia graveco de la problemo de haltado (mensogoj, mensogas, kuŝas) en la fakto (tiu, ke, kiu) ĝi estis unu de la unua (problemoj, problemas) al esti (pruvita, pruvis) nedecidebla. (Turing-a's pruvo iris al premi en (Majo, Povas) 1936, (dum, ĉar) (Eklezia, Kirka, Preĝeja) pruvo de la _undecidability_ de problemo en la lambda kalkulo havis jam estas (publikigita, publikigis) en Aprilo 1936.) Sinsekve, multaj alia tia (problemoj, problemas) havi estas priskribita; la tipa maniero de pruvanta problemo al esti nedecidebla estas kun la tekniko de malpligrandiĝo. Al fari ĉi tiu, la komputila sciencisto montras (tiu, ke, kiu) se solvaĵo al la nova problemo estis fundamenti, ĝi povis kutimi decidi nedecidebla problemo (per konvertanta (aper(aĵ)oj, aper(aĵ)as) de la nedecidebla problemo enen (aper(aĵ)oj, aper(aĵ)as) de la nova problemo). Ekde ni jam scii (tiu, ke, kiu) ne maniero povas decidi la malnova problemo, ne maniero povas decidi la nova problemo ĉu.

Unu tia konsekvenco de la problemo de haltada _undecidability_ estas (tiu, ke, kiu) tie ne povas esti ĝenerala algoritmo (tiu, ke, kiu) decidas ĉu donita (propozicio, frazo, ordono) pri naturaj nombroj estas vera ĉu ne. La kaŭzo por ĉi tiu estas (tiu, ke, kiu) la propozicio (tiu, ke, kiu) ŝtatoj (tiu, ke, kiu) certa algoritmo estos halti donita certa (enigo, enigi) povas esti konvertita enen ekvivalento (propozicio, frazo, ordono) pri naturaj nombroj. Se ni havita algoritmo (tiu, ke, kiu) povis solvi (ĉiu, iu) (propozicio, frazo, ordono) pri naturaj nombroj, ĝi povis certe solvi ĉi tiu unu; sed (tiu, ke, kiu) devus difini ĉu la originala programo (digas, endigigas, haltas), kiu estas neebla, ekde la problemo de haltado estas nedecidebla.

Ankoraŭ alia, sufiĉe miriga, konsekvenco de la _undecidability_ de la problemo de haltado estas Rizaj teoremaj kiuj ŝtatoj (tiu, ke, kiu) la vero de (ĉiu, iu) ne-bagatela (propozicio, frazo, ordono) pri la funkcia tio estas difinita per algoritmo estas nedecidebla. (Do, Tiel), ekzemple, la decida problemo "estos ĉi tiu algoritmo halti por la (enigo, enigi) 0" estas jam nedecidebla. (Tononomo, Noto, Noti) (tiu, ke, kiu) ĉi tiu teoremo tenas por la funkcio difinis per la algoritmo kaj ne la algoritma sin. Ĝi estas, ekzemple, sufiĉe ebla al decidi se algoritmo estos halti en 100 (ŝtupoj, ŝtupas, paŝas), sed ĉi tiu estas ne (propozicio, frazo, ordono) pri la funkcia tio estas difinita per la algoritmo.

_Gregory_ _Chaitin_ havas donita nedecidebla problemo en algoritma informa teorio kiu ne dependi sur la problemo de haltado. _Chaitin_ ankaŭ donis la (intriganta, komplotanta) difino de la haltanta probablo kiu prezentas la probablo (tiu, ke, kiu) hazarde produktis programo (digas, endigigas, haltas).

Dum Turing-a's pruvo montras (tiu, ke, kiu) tie povas esti ne ĝenerala maniero aŭ algoritmo al difini ĉu (algoritmoj, algoritmas) halti, persona (aper(aĵ)oj, aper(aĵ)as) de (tiu, ke, kiu) problemo (majo, povas) bonege esti _susceptible_ al ataki. Donita specifa algoritmo, unu povas ofte montri (tiu, ke, kiu) ĝi devas halti por (ĉiu, iu) (enigo, enigi), kaj fakte komputilo (sciencistoj, sciencistas) ofte fari (justa, ĵus) (tiu, ke, kiu) kiel parto de praveca pruvo. Sed ĉiu tia pruvo postulas nova (argumentoj, argumentas): estas ne mekanika, ĝenerala vojo al difini ĉu (algoritmoj, algoritmas) sur Maŝino de Turing halti. Tamen, estas iu (heŭristikoj, heŭristikas) (tiu, ke, kiu) povas esti uzita en aŭtomatis (modo, maniero) al provi al konstrui pruvo, kiu sukcesi ofte sur tipaj programoj. Ĉi tiu kampo de esplori estas sciata kiel aŭtomatis finiga analitiko.

Estas alia _caveat_. La _undecidability_ de la problemo de haltado fidas sur la fakto (tiu, ke, kiu) (algoritmoj, algoritmas) estas alprenita al havi potencialhave malfinia memoro: je (ĉiu, iu) unufoje ili povas nur butiko finie multaj aĵoj, sed ili povas ĉiam butiko pli kaj ili neniam kuri el memoro. Tamen, komputiloj (tiu, ke, kiu) reale ekzisti estas ne ekvivalento al Maŝino de Turing sed anstataŭe al lineara barita aŭtomato, kiel ilia memoro kaj ekstera memoro de maŝino estas (limigita, limigis). En ĉi tiu (kesto, okazo), la problemo de haltado por programoj (kuro, kurante, rulante) sur (tiu, ke, kiu) maŝino povas esti solvita kun tre simpla ĝenerala algoritmo (_albeit_ unu tio estas (do, tiel) _inefficient_ (tiu, ke, kiu) ĝi povis neniam esti utila en praktiko). Ĝi engaĝas (kuro, kurante, rulante) la programo kaj (penanta, provanta, penante) al trovi ciklo super la ŝtatoj de la (maŝina, aparata) memoro.

Turing-a's enkonduko de la maŝina modelo (tiu, ke, kiu) havas iĝi sciata kiel la Maŝino de Turing, prezentis en la papero, havas (pruvita, pruvis) oportuna modelo por multa teoria komputiko ekde.

[redaktu] Skizi de pruvo

La pruvo procedas per redukto al absurdo. Starti per elektanta programlingvo, projekto (tiu, ke, kiu) (asociitoj, asociitas, asocianoj, asocianas, kompanianoj, kompanianas) ĉiu programo kun almenaŭ unu linia priskribo. Nun supozi (tiu, ke, kiu) iu pretendas al havi fundamenti algoritmo <kodo>halti(a, mi)</kodo> (tiu, ke, kiu) redonas <kodo>vera</kodo> se a priskribas programo (tiu, ke, kiu) (digas, endigigas, haltas) kiam donita kiel (enigo, enigi) la linio mi, kaj redonas <kodo>malvera</kodo> alie. Konstrui alia programo <kodo>(ĝeni, ĝen(aĵ)o)</kodo> (tiu, ke, kiu) uzas <kodo>halti</kodo> kiel proceduro (subprogramo:

funkcio (ĝeni, ĝen(aĵ)o)(linio s)
se halti(s, s) == malvera
redoni vera
alia
ciklo eterne

Ĉi tiu programo prenas linio s kiel ĝia argumento kaj (kuras, rulas) la algoritmo <kodo>halti</kodo>, donanta ĝi s ambaŭ kiel la priskribo de la programo al kontroli kaj kiel la komencaj datumoj al nutri al (tiu, ke, kiu) programo. Se <kodo>halti</kodo> redonas <kodo>malvera</kodo>, tiam <kodo>(ĝeni, ĝen(aĵ)o)</kodo> redonas vera, alie <kodo>(ĝeni, ĝen(aĵ)o)</kodo> iras enen malfinia ciklo. Ekde ĉiuj programoj povas esti (prezentita, prezentis) per (surfadenigas, kordoj, kordas, ĉenoj, ĉenas, linioj, linias), estas linio t (tiu, ke, kiu) prezentas la programo <kodo>(ĝeni, ĝen(aĵ)o)</kodo>. Faras <kodo>(ĝeni, ĝen(aĵ)o)(t)</kodo> halti?

Konsideri ambaŭ (okazoj, skatoloj, kestoj, kestas, okazas):

1. Se <kodo>(ĝeni, ĝen(aĵ)o)(t)</kodo> (digas, endigigas, haltas), ĝi devas esti ĉar <kodo>halti(t, t)</kodo> redonis <kodo>malvera</kodo>, sed (tiu, ke, kiu) devus (meznombro, signifi) (tiu, ke, kiu) <kodo>(ĝeni, ĝen(aĵ)o)(t)</kodo> devus ne havi (digita, endigigita, haltita).
2. Se <kodo>(ĝeni, ĝen(aĵ)o)(t)</kodo> (kuras, rulas) eterne, ĝi estas ĉu ĉar <kodo>halti</kodo> sin (kuras, rulas) eterne, aŭ ĉar ĝi redonis <kodo>vera</kodo>. Ĉi tiu devus (meznombro, signifi) ĉu (tiu, ke, kiu) <kodo>halti</kodo> ne laboro por ĉiu valida (enigo, enigi), aŭ (tiu, ke, kiu) <kodo>(ĝeni, ĝen(aĵ)o)(t)</kodo> devus havi (digita, endigigita, haltita).

Ĉu (kesto, okazo) konkludas (tiu, ke, kiu) <kodo>halti</kodo> farita ne doni (ĝusta, ĝustigi, korekti) (respondo, respondi), kontraŭ la originala pretendi. Ekde la sama (racianta, rezonanta, kaŭzanta) aplikas al (ĉiu, iu) programo (tiu, ke, kiu) iu povus (oferi, oferti) kiel solvaĵo al la problemo de haltado, tie povas esti ne solvaĵo.

Ĉi tiu klasika pruvo estas tipe referita al kiel la diagonaliga pruvo, (do, tiel) (nomita, vokis) ĉar se unu imagas krado enhavanta ĉiu (valoroj, valoras) de <kodo>halti(a, mi)</kodo>, kun ĉiu ebla a valoro donita ĝia posedi (linio, vico), kaj ĉiu ebla mi valoro donita ĝia posedi kolumno, tiam la (valoroj, valoras) de <kodo>halti(s, s)</kodo> estas aranĝita laŭ la ĉefa diagonalo de ĉi tiu krado. La pruvo povas esti (enkadrigita, kadrita) en la (formo, formi) de la demando: kio (linio, vico) de la krado korespondas al la linio t? La (respondo, respondi) estas (tiu, ke, kiu) la <kodo>(ĝeni, ĝen(aĵ)o)</kodo> funkcio estas _devised_ tia (tiu, ke, kiu) <kodo>halti(t, mi)</kodo> diferencas de ĉiu (linio, vico) en la krado en almenaŭ unu pozicio: nome, la ĉefa diagonalo, kie t=mi. Ĉi tiu kontraŭdiras la bezono (tiu, ke, kiu) la krado enhavas (linio, vico) por ĉiu ebla a valoro, kaj pro tio konsistigas pruvo per kontraŭdiro (tiu, ke, kiu) la problemo de haltado estas nedecidebla.

[redaktu] Komuna _pitfalls_

Multaj studentoj, sur analizanta la pli supre pruvo, (demandi, peti) ĉu tie povus esti algoritmo (tiu, ke, kiu) povas redoni tria alternativo por iuj programoj, kiel "nedecidebla" aŭ "devus (plumbo, konduki) al kontraŭdiro." Ĉi tiu reflektas miskomprenanta de decideblo. Ĝi estas facila al konstrui unu algoritmo (tiu, ke, kiu) ĉiam (respondoj, respondas) "(digas, endigigas, haltas)" kaj alia (tiu, ke, kiu) ĉiam (respondoj, respondas) "ne halti." Por (ĉiu, iu) specifa programo kaj (enigo, enigi), unu de ĉi tiuj du (algoritmoj, algoritmas) (respondoj, respondas) ĝuste, (eĉ, ebena, para) kvankam neniu (majo, povas) scii kiu. La malfacilaĵo de la problemo de haltado (mensogoj, mensogas, kuŝas) ne en apartaj programoj, sed en la bezono (tiu, ke, kiu) solvaĵo devas laboro por ĉiuj programoj.

Ĝi estas valori notanta (tiu, ke, kiu) la problemo de haltado estas decidebla por (determinisma, determina) (maŝinoj, maŝinas, aparatoj, aparatas) kun finia memoro. Maŝino kun finia memoro havas finia nombro de ŝtatoj, kaj tial (ĉiu, iu) (determinisma, determina) programo sur ĝi devas eble ĉu halti aŭ ripeti antaŭa (ŝtato, stato, stati). Ripetado de antaŭa (ŝtato, stato, stati) indikas ciklo, (do, tiel) programo (tiu, ke, kiu) ripetas antaŭa (ŝtato, stato, stati) estas tial sciata al ne halti.

[redaktu] Formaligo de la problemo de haltado

En lia originala pruvo Turing-a formaligis la koncepto de algoritmo per prezentantaj Turingaj aŭtomatoj. Tamen, la rezulto estas neniel specifa al ili; ĝi aplikas egale al (ĉiu, iu) alia modelo de kalkulada tio estas ekvivalento en ĝia komputa povo al Turingaj aŭtomatoj, kiel Markovaj algoritmoj, Lambda kalkulo, (Afiŝo, Posteno) sistemoj aŭ registraj maŝinoj.

Kio estas grava estas (tiu, ke, kiu) la formaligo permesas simpla surĵeto de (algoritmoj, algoritmas) al iu datumtipo (tiu, ke, kiu) la algoritmo povas operacii sur. Ekzemple, se la formalismo lasas (algoritmoj, algoritmas) difini funkcioj super (surfadenigas, kordoj, kordas, ĉenoj, ĉenas, linioj, linias) (kiel Turingaj aŭtomatoj) tiam tie devus esti surĵeto de ĉi tiuj (algoritmoj, algoritmas) al (surfadenigas, kordoj, kordas, ĉenoj, ĉenas, linioj, linias), kaj se la formalismo lasas (algoritmoj, algoritmas) difini funkcioj super naturaj nombroj (kiel rekursiaj funkcioj) tiam tie devus esti surĵeto de (algoritmoj, algoritmas) al naturaj nombroj. La surĵeto al (surfadenigas, kordoj, kordas, ĉenoj, ĉenas, linioj, linias) estas kutime la plej simpla, sed (surfadenigas, kordoj, kordas, ĉenoj, ĉenas, linioj, linias) super alfabeto kun n signoj povas ankaŭ esti mapita al nombroj per (interpretado, interpretanta) ilin kiel nombroj en n-_ary_ numeralo.

[redaktu] Interrilato kun Teoremoj de nekompleteco

La (konceptoj, konceptas) altigita per (Teoremoj de nekompleteco, Teoremojj de nekompleteco) estas tre simila al tiuj altigita per la problemo de haltado, kaj la pruvoj estas sufiĉe simila. Fakte, (pli lama, pli malforta) (formo, formi) de la Unua Nepleneca Teoremo estas facila konsekvenco de la _undecidability_ de la problemo de haltado. Ĉi tiu (pli lama, pli malforta) (formo, formi) diferencas de la normo (propozicio, frazo, ordono) de la nepleneca teoremo per asertanta (tiu, ke, kiu) plenumi, konsekvenca kaj sono aksiomigo de ĉiuj (propozicioj, frazoj, ordonoj) pri naturaj nombroj estas _unachievable_. La "sono" parto estas la malfortiganta: ĝi (meznombroj, meznombras, signifas) (tiu, ke, kiu) ni postuli la aksiomaro koncerna al pruvi nur vera (propozicioj, frazoj, ordonoj) pri naturaj nombroj (ĝi's tre grava al observi (tiu, ke, kiu) la (propozicio, frazo, ordono) de la normo (formo, formi) de Gödel-a's Unua Nepleneca Teoremo estas plene _unconcerned_ kun la demando de vero, sed nur koncernas la (eldoni, eligo) de ĉu ĝi povas esti pruvita).

La (pli lama, pli malforta) (formo, formi) de la teoremo povas esti (pruvita, pruvis) de la _undecidability_ de la problemo de haltado kiel sekvas. Alpreni (tiu, ke, kiu) ni havi konsekvenca kaj plenumi aksiomigo de ĉiu vera logiko de la unua ordo (propozicioj, frazoj, ordonoj) pri naturaj nombroj. Tiam ni povas (masoni, ĉarpenti, konstrui) algoritmo (tiu, ke, kiu) _enumerates_ ĉiuj ĉi tiuj (propozicioj, frazoj, ordonoj). Ĉi tiu (meznombroj, meznombras, signifas) (tiu, ke, kiu) estas algoritmo N(n) (tiu, ke, kiu), donita natura nombro n, komputas vera logiko de la unua ordo (propozicio, frazo, ordono) pri naturaj nombroj tia (tiu, ke, kiu), por ĉiu vera (propozicioj, frazoj, ordonoj), estas almenaŭ unu n tia (tiu, ke, kiu) N(n) rendimento (tiu, ke, kiu) (propozicio, frazo, ordono). Nun supozi ni bezono al decidi se la algoritmo kun prezento a (digas, endigigas, haltas) sur (enigo, enigi) mi. Ni scii (tiu, ke, kiu) ĉi tiu (propozicio, frazo, ordono) povas esti esprimita kun logiko de la unua ordo (propozicio, frazo, ordono), diri H(a, mi). Ekde la aksiomigo estas plenumi ĝi sekvas (tiu, ke, kiu) ĉu estas n tia (tiu, ke, kiu) N(n) = H(a, mi) aŭ estas n' tia (tiu, ke, kiu) N(n') = ¬ H(a, mi). (Do, Tiel) se ni ripeti super ĉiuj n ĝis ni ĉu trovi H(a, mi) aŭ ĝia nego, ni estos ĉiam halti. Ĉi tiu (meznombroj, meznombras, signifas) (tiu, ke, kiu) ĉi tiu donas ni algoritmo al decidi la problemo de haltado. Ekde ni scii (tiu, ke, kiu) tie ne povas esti tia algoritmo, ĝi sekvas (tiu, ke, kiu) la (premiso, supozo) (tiu, ke, kiu) estas konsekvenca kaj plenumi aksiomigo de ĉiu vera logiko de la unua ordo (propozicioj, frazoj, ordonoj) pri naturaj nombroj devas esti malvera.

[redaktu] Povas (homoj, homas) solvi la problemo de haltado?

Ĝi povus aspekti ŝati (homoj, homas) povita solvi la problemo de haltado. Post ĉiuj, (programisto, komputisto) povas ofte rigardi programo kaj diri ĉu ĝi estos halti. Ĝi estas utila al kompreni kial ĉi tiu ne povas esti vera. Por simpleco, ni estos konsideri la problemo de haltado por programoj sen (enigo, enigi), kiu estas ankaŭ nedecidebla.

Al "solvi" la problemo de haltado (meznombroj, meznombras, signifas) povi rigardi (ĉiu, iu) programo kaj diri ĉu ĝi (digas, endigigas, haltas). Ĝi estas ne sufiĉa povi rigardi iu programoj kaj decidi. (Homoj, Homas) (majo, povas) ankaŭ ne kapabli solvi la problemo de haltado, pro al la kruta amplekso de la (enigo, enigi) (programo kun (milionoj, milionas) de linioj de kodo). (Eĉ, Ebena, Para) por mallongaj programoj, ĝi _isn_'t klara (tiu, ke, kiu) (homoj, homas) povas ĉiam diri ĉu ili halti. Ekzemple, ni povus (demandi, peti) se ĉi tiu _pseudocode_ funkcio, kiu korespondas al aparta Maŝino de Turing, iam (digas, endigigas, haltas):

funkcio _searchForOddPerfectNumber_()
_var_ _int_ n:=1 // ajna-precizeca entjero
ciklo {
_var_ _int_ _sumOfFactors_ := 0
por faktoro de 1 al n-1
se faktoro estas faktoro de n
_sumOfFactors_ := _sumOfFactors_ + faktoro
se _sumOfFactors_ = n tiam
elireja ciklo
n := n + 2
}
redoni

Ĉi tiu programo (serĉadoj, serĉoj) ĝis ĝi trovas nepara perfekta nombro, tiam (digas, endigigas, haltas). Ĝi (digas, endigigas, haltas) se kaj nur se tia nombro ekzistas, kiu estas majoro (malfermi, malfermita) demando en matematiko. (Do, Tiel), post (jarcentoj, jarcentas) de laboro, (matematikistoj, matematikistas) havi ankoraŭ al (malkovri, esplori) ĉu simpla, dek-linia programo (digas, endigigas, haltas). Ĉi tiu (konstruas, faras) ĝi malfacila al vidi kiel (homoj, homas) povita solvi la problemo de haltado.

Pli ĝenerale, ĝi's kutime facila al vidi kiel al skribi simpla bruto-forto (serĉi, serĉo) programo (tiu, ke, kiu) (aspektas, aspektoj, rigardas) por (kontraŭekzemploj, kontraŭekzemplas) al (ĉiu, iu) aparta konjekto en nombroteorio; se la programo trovas kontraŭekzemplo, ĝi (digas, endigigas, haltas) kaj (presas, printas) ekster la kontraŭekzemplo, kaj alie ĝi konservas serĉanta eterne. Ekzemple, konsideri la fama (kaj ankoraŭ nesolvita) ĝemela prima konjekto. Ĉi tiu (demandas, petas) ĉu estas arbitre grandaj primoj p kaj q kun p+2 = q. Nun konsideri jena programo, kiu akceptas (enigo, enigi) N:

funkcio _findTwinPrimeAbove_(_int_ N)
_int_ p := N
ciklo
se p estas primo kaj p + 2 estas primo
redoni
alia
p := p + 1

Ĉi tiu programo (serĉadoj, serĉoj) por ĝemelaj primoj p kaj p+2 ambaŭ almenaŭ kiel granda kiel N. Se estas arbitre grandaj ĝemelaj primoj, ĝi estos halti por ĉiuj ebla (enigoj, enigas). Sed se estas paro de ĝemelaj primoj P kaj P+2 pli granda ol ĉiuj aliaj ĝemelaj primoj, tiam la programo estos neniam halti se ĝi estas donita (enigo, enigi) N pli granda ol P. Tial se ni povita (respondo, respondi) la demando de ĉu ĉi tiu programo (digas, endigigas, haltas) sur ĉiuj (enigoj, enigas), ni devus havi la longa-_sought_ esti konforma al la ĝemela prima konjekto. Ĝi's simile simpla al skribi programoj kiu halti dependanta sur la vero aŭ _falsehood_ por multaj alia (konjektoj, konjektas) de nombroteorio.

Pro ĉi tiu, unu povus diri (tiu, ke, kiu) la haltanta teorema sin estas _unsurprising_. Se tie estis mekanika vojo al decidi ĉu ajnaj programoj devus halti, tiam multaj (evidente, aparte, videble) malfacilaj matematikaj problemoj devus subfali al ĝi. _Counterargument_ al ĉi tiu, tamen, estas (tiu, ke, kiu) eĉ se la problemo de haltado estis decidebla super Turingaj aŭtomatoj, kiel ĝi estas super fizikaj komputiloj kaj alia _LBAs_, ĝi povus ankoraŭ esti _infeasible_ en praktiko ĉar ĝi prenas tra tempo aŭ memoro al (ekzekuti, plenumit). Ekzemple, estas iu tre grandaj superaj baroj sur nombroj kun certaj propraĵoj en nombroteorio, sed ĝi's ne farebla al kontroli ĉiuj (valoroj, valoras) pli sube ĉi tiu baro en _naïve_ vojo kun komputilo — ili povas't (eĉ, ebena, para) teni iu de ĉi tiuj nombroj en memoro.

[redaktu] Agnoskantaj partaj solvaĵoj

Estas multaj programoj (tiu, ke, kiu) ĉu redoni (ĝusta, ĝustigi, korekti) esti konforma al la problemo de haltado aŭ ne redoni (respondo, respondi) ajn. Se ĝi estis ebla al decidi ĉu programo donas nur (ĝusta, ĝustigi, korekti) (respondoj, respondas), unu povus esperi al kolekti granda nombro de tiaj programoj kaj kuri ilin en paralelo, en la esperi de estante pova difini ĉu multaj programoj halti. Bedaŭrinde, agnoskanta tia parta haltanta (solviloj, solvas) (_PHS_) estas (justa, ĵus) kiel peza kiel la problemo de haltada sin.

Supozi iu pretendas (tiu, ke, kiu) programo _PHSR_ estas parta haltanta solvilo _recognizer_. Konstrui programo H:

(enigo, enigi) programo P
X := "(enigo, enigi) Q. se Q = P (eligi, eligo) "(digas, endigigas, haltas)" alia ciklo eterne"
kuri _PHSR_ kun X kiel (enigo, enigi)

Se _PHSR_ agnoskas la konstruis programo X kiel parta haltanta solvilo, (tiu, ke, kiu) (meznombroj, meznombras, signifas) (tiu, ke, kiu) P, la nur (enigo, enigi) por kiu X produktas rezulto, (digas, endigigas, haltas). Se _PHSR_ mankas al agnoski X, tiam ĝi devas esti ĉar P ne halti. Pro tio H povas decidi ĉu ajna programo P (digas, endigigas, haltas); ĝi solvas la problemo de haltado. Ekde ĉi tiu estas neebla, la programo _PHSR_ povis ne havi estas parta haltanta solvilo _recognizer_ kiel pretendis. Pro tio ne programo povas esti parta haltanta solvilo _recognizer_.

Alia ekzemplo, H_T, de Maŝino de Turing kiu donas (ĝusta, ĝustigi, korekti) (respondoj, respondas) nur por iu (aper(aĵ)oj, aper(aĵ)as) de la problemo de haltado povas esti priskribita per la (postuloj, bezonoj, bezonas) (tiu, ke, kiu), se H_T estas startita (skanadanta, skananta, skandanta) kampo kiu (portoj, portas) la unua de finia linio de a najbara "1"s, sekvis per unu kampo kun simbolo "0" (mi. e. formulara kampo), kaj sekvis laŭvice per finia linio de mi najbara "1"s, sur alie formulara bendo, tiam

• H_T (digas, endigigas, haltas) por (ĉiu, iu) tia startanta (ŝtato, stato, stati), mi. e. por (ĉiu, iu) (enigo, enigi) de finia pozitiva (entjeroj, entjeras) a kaj mi;
• H_T (digas, endigigas, haltas) sur plene formularo bendo se kaj nur se la Maŝino de Turing (prezentita, prezentis) per a ne halti kiam donita la startanta (ŝtato, stato, stati) kaj (enigo, enigi) (prezentita, prezentis) per mi; kaj
• H_T (digas, endigigas, haltas) sur _nonblank_ bendo, (skanadanta, skananta, skandanta) adekvata kampo (kiu tamen ne bezone (porto, porti) la simbolo "1") se kaj nur se la Maŝino de Turing (prezentita, prezentis) per a faras halti kiam donita la startanta (ŝtato, stato, stati) kaj (enigo, enigi) (prezentita, prezentis) per mi. En ĉi tiu (kesto, okazo), la fina (ŝtato, stato, stati) en kiu H_T (digis, endigigita, haltita) ((enhavoj, enhavas) de la bendo, kaj kampo estante (skanadis, skanita, skandita)) estos esti egala al iu aparta intera (ŝtato, stato, stati) kiu la Maŝino de Turing (prezentita, prezentis) per a atingas kiam donita la startanta (ŝtato, stato, stati) kaj (enigo, enigi) (prezentita, prezentis) per mi; aŭ, se ĉiuj tiuj interaj ŝtatoj (inkluzivanta la startanta (ŝtato, stato, stati) (prezentita, prezentis) per mi) lasi la benda formularo, tiam la fina (ŝtato, stato, stati) en kiu H_T (digis, endigigita, haltita) estos esti (skanadanta, skananta, skandanta) "1" sur alie formulara bendo.

Dum ĝia ekzisto havas ne estas refutita (esence: ĉar tie's ne Maŝino de Turing kiu devus halti nur se startis sur formulara bendo), tia Maŝino de Turing H_T devus solvi la problemo de haltado nur parte ĉu (ĉar ĝi ne bezone (skanado, skani, skandi) la simbolo "1" en la fina (ŝtato, stato, stati), se la Maŝino de Turing (prezentita, prezentis) per a faras halti kiam donita la startanta (ŝtato, stato, stati) kaj (enigo, enigi) (prezentita, prezentis) per mi, kiel eksplicita (propozicioj, frazoj, ordonoj) de la problemo de haltado por Turingaj aŭtomatoj (majo, povas) postuli).

[redaktu] Historio de la problemo de haltado

En jeno: U (ligas, referas) al la fonto "Nedecidebla"

1900 -- Hilberto afektas lia "23 (demandoj, demandas)" cf Hilberto (problemoj, problemas) je la 2-a Internacia Kongreso de (Matematikistoj, Matematikistas) en Parizo, "De ĉi tiuj, la (sekundo, dua) estis (tiu, ke, kiu) de pruvanta la konsekvenco de la 'Aksiomoj de peano' sur kiu, kiel li havis montrita, la rigoro de matematiko dependis" (_Hodges_ p.83, komentaro en U p. 108; ankaŭ _Penrose_ p. 34; ankaŭ lia adreso La Estonto de Matematiko represis en _Reid_ p. _74ff_ kaj lia fama _pronouncement_: "Ĉi tiu konvinko de la solvebleco de ĉiu matematika problemo estas pova instigilo al la laborabelo. Ni aŭdi en ni la _perpetual_ (voko, voki): Estas la problemo. (Strebi, Kandidati) ĝia solvaĵo. Vi povas trovi ĝi per pura kaŭzo, por en matematiko, estas ne _ignorabimus_"(_ibid_ p. 81)

1928 -- Hilberto _recasts_ lia '(Sekundo, Dua) Problemo' [(priprograma pruv(ad)o, kontrolo) postulis! cf _Penrose_ p.34 ŝtatoj ĉi tiu estas _recast_ de lia 10-a problemo sed _Reid_ ne (kongrui, konsenti)] je la Bolonja Internacia Kongreso (cf _Reid_ _pp_.188-189). "Hilberto nun adiciis al la problemo de konsekvenca alia problemo, (tiu, ke, kiu) de la pleneco de la formala sistemo" (p. 189 _Reid_). _Hodges_ pretendas li afektis tri (demandoj, demandas): kio estas #1: Estita matematiko plenumi? #2: Estita matematiko konsekvenca? #3: Estis matematiko decidebla? (_Hodges_ p. 91). La tria demando estas sciata kiel la _Entscheidungsproblem_ (Decida Problemo) (_Hodges_ p.91, _Penrose_ p.34)

1930 -- Hilberto emeritiĝas, liveras lia "Adiaŭ al Instruanta" (_Reid_ p. 190) kaj _reaffirms_ lia "_Positivist_ konvinko" (_Hodges_ p. 92) (tiu, ke, kiu) "...estas ne tia aĵo kiel _unsolvable_ problemo." (Hilberto citis en _Hodges_ p.92). "...li malkonsentis denove, je la fino de lia kariero, la "malsaĝa _ignorabimus_" de _du_ _Boita_-_Reymond_ kaj lia (adeptoj, adeptas). Je preskaŭ la sama tempo [ankoraŭ (bezonas, bezonoj) (priprograma pruv(ad)o, kontrolo)] Gödel-a anoncas lia pruvo kiel esti konforma al la unua du de Hilberta 1928 (demandoj, demandas) [cf _Reid_ p. 198]. Gödel-a's papero estas ricevita sur 17 Novembro (U p.5). "Komence li [Hilberto] estis nur koleri kaj frustris, sed tiam li komencita al provi al kontrakto konstrue kun la problemo... _Göodel_ sin felto-- kaj esprimita la penso en lia papero -- (tiu, ke, kiu) lia laboro farita ne kontraŭdiri Hilberta _formalistic_ punkto de vido" (_Reid_ p. 199).

1931 -- La papero de Kurt Gödel (aperas, ŝajnas, aspektas): "Sur Formale Nedecidebla (Propozicioj, Propozicias) de Principoj Mathematica kaj Rilatantaj Sistemoj Mi", (represita en U p. 5 _ff_)

19 Aprilo 1935 -- Papero de Alonzo Church "An _Unsolvable_ Problemo de Rudimenta Nombra Teorio" estas (surscenigita, enscenigita, prezentita) al la Amerika Matematika Socio, (represis en U p. _89ff_). Preĝejo identigas efika _caluclability_ kun "la nocio de rekursia funkcio de pozitiva (entjeroj, entjeras)" (U p. 100). Tia funkcio estos havi algoritmo, kaj "...la fakto (tiu, ke, kiu) la algoritmo havas finita [_italics_ adiciis] iĝas efike sciata kaj la valoro de F(n) estas efike _calculable_" (_ibid_).

1936 -- Alonzo Church _publishes_ la unua pruvo (tiu, ke, kiu) la _Entscheidungsproblem_ estas _unsolvable_ [A (Tononomo, Noto, Noti) sur la _Entsheidungsproblem_, represis en U p.110].

7 Oktobro 1936 -- Papero de _Emil_ (Afiŝo, Posteno) estas ricevita per Preĝejo’s (_Hodges_ p. 125) Ĵurnalo de Signa Logiko. Lia papero aperita kiel "Finiaj Kombinaj Procezoj. Formulaĵo Mi",(represita en U p. _298ff_). (Afiŝa, Postena) lakona papero prezentas la vorto "fini”. Preĝejo havis al jesigi (tiu, ke, kiu) (Afiŝo, Posteno) estis _unaware_ de Turing-a's laboro kaj (malvirto, ŝraŭbtenilo) _versa_ (cf komentaro en U p. 288, ankaŭ _Hodges_ p. 125). Vidi Piednoto|(Afiŝo, Posteno).

Januaro 1937 -- Turing-a's Sur Komputeblaj Nombroj Kun Apliko al la _Entscheidungsproblem_ estas (publikigita, publikigis) (represita en U, p. 115). Kun tri (teoremoj, teoremas) li (respondoj, respondas) la “decida problemo”: "Mi estos montri (tiu, ke, kiu) estas ne ĝenerala maniero kiu diras ĉu donita formulo U estas demonstrebla en K [Principoj Mathematica], aŭ kio venas al la sama, ĉu la sistemo konsistanta de K kun -U aligita kiel superflua aksiomo estas konsekvenca" (p. 145, _ibid_). Vidi Piednoto|Turing-a.

1939 -- J.B. _Rosser_ observas la esenca ekvivalento de "efika maniero" difinis per Gödel-a, Preĝejo, kaj Turing-a (_Rosser_ en U p. 273, "Neformala Ekspozicio de Pruvoj de Gödel-a's Teoremo kaj (Eklezia, Kirka, Preĝeja) Teoremo"].

1943 -- En lia 1943 papero _Stephen_ Kleene-aj diskutoj "algoritma (teorioj, teorias)" ("Rekursie (Predikatoj, Predikatas) kaj (Kvantoroj, Kvantumiloj, Kvantumas)", represita en U _pp_. _255ff_). Liaj ŝtatoj (tiu, ke, kiu) "En opcio supren plenumi algoritma teorio, kio ni fari estas priskribi proceduro ... kiu proceduro bezone finas kaj en tia maniero (tiu, ke, kiu) de la rezulto ni povas legi definitiva (respondo, respondi), "Jes" aŭ "Ne," al la demando, "Estas la predikata valoro vera?"

[redaktu] Piednotoj

Piednoto|_Davis_: Turing-a farita ne uzi la vorto "haltanta" aŭ "finigo". Turing-a's biografo _Hodges_ ne havi la vorto "haltanta" aŭ (vortoj, vortas) "problemo de haltado" en lia indekso. La plaj frua sciata uzi de la (vortoj, vortas) "problemo de haltado" estas en pruvo per _Davis_ (p. 70-71, _Davita_ 1958). Li uzas _Gödelization_ al pruvi la teoremo:

"Teoremo 2.2 Tie ekzistas Maŝino de Turing kies problemo de haltado estas rekursie _unsolvable_.

"A rilatanta problemo estas la (presanta, printanta) problemo por simpla Maŝino de Turing Z kun respekto al simbola Si" (p. 70).

_Davita_ tiam iras sur al pruvi lia Teoremo 2.3 (tiu, ke, kiu) "...la (presanta, printanta) problemo por Z kun respekto al _Sk_ estas rekursie _unsolvable_" (p. 71). Ĉi tiu pruvo uzas (formo, formi) simila al la _antinomies_ (tiu, ke, kiu) aperi en _Minsky_, _Beltrami_ kaj ĉi tiu paĝo, pli supre. _Davita_ adicias ne _attribution_ por ĉi tiuj pruvoj, (do, tiel) ni povas konkludi ili estas originala kun lin.

"Haltanta Problemo" ne aperi en ĉu de Alonzo Church's (tekstoj, tekstas) (datita, rendevuita, daktilarbita, daktilujita, daktita) 1944 kaj 1956, nek en E.F. Stepoj' A (Simpligis, Plisimpligita) Universala Turing-a Maŝino, _Proc_. _ACM_, _Sept_ 1952, 1953. _Moore_'s paperaj referencoj "_mimeographed_ (tononomoj, notoj, notas)" de prelego per _Davis_ je la Universitato de Ilinojo en 1951, (do, tiel) ĉi tiu fonto devus (bezoni, bezono, necesa) al esti esplorita. _Hao_ _Wang_'s A (Rikorda kazo, Varianto) al Turing-a's Teorio de Komputanta (Maŝinoj, Maŝinas, Aparatoj, Aparatas), Ĵurnalo de la _ACM_ 4(1):63-92 Januaro 1957 faras mencii "halti" kiel komando (p. 65), sed ne la "problemo de haltado." _Wang_ laŭvice referencoj (Afiŝo, Posteno) (_ibid_); vidi Piednoto|(Afiŝo, Posteno) pli sube. Per 1965 la "problemo de haltado" havas aperita en Fiŝisto, Sur (formalismoj, formalismas) por Turing-a (Maŝinoj, Maŝinas, Aparatoj, Aparatas), Ĵurnalo de la _ACM_ 12,4 (_Oct_ 1965), _Anderaa_ & Fiŝisto, La Solvebleco de la Haltanta Problemo por du (ŝtato, stato, stati) (Afiŝo, Posteno) (Maŝinoj, Maŝinas, Aparatoj, Aparatas), Ĵurnalo de la _ACM_ 14(4):677-682 (_Oct_ 1967), kaj en _Minsky_'s teksto (1967).

Piednoto|(Afiŝo, Posteno): En lia papero (Afiŝo, Posteno) priskribas "formulaĵo" (kio estas procezo, ne maŝino) konsistanta de "laborabelo" kiu sekvas "aro de (komandoj, komandas, instrukcio)" ((komandoj, komandas, instrukcio) (tiu, ke, kiu) estas, kiel ĝi (turnita, turnis) ekster, virtuale identa al tiuj de Turing-a's (maŝinoj, maŝinas, aparatoj, aparatas)). Sed (Afiŝo, Posteno) adicias alia komando "(C) Halti". Tial "...Ĉi tiu procezo estos fini kiam kaj nur kiam ĝi venas al la direkto de tipo (C)." Li (nomita, vokis) tia procezo "tipo 1 ... se la proceza ĝi difinas finas por ĉiu specifa problemo." Li iris sur al forpreni la "Halti" komando kiam (komputanta, pritaksanta) "signaj logikoj"; en ĉi tiu (kesto, okazo) "(determinisma, determina) procezo estos esti konstrui kiu estas _unending_" [lia _italics_] (Afiŝo, Posteno) farita ne adreso rekte la "_Entscheidungsproblem_" en lia "formulaĵo"; vidi (Afiŝo, Posteno)-Turing-a Maŝino por pli.

[redaktu] Referencoj

• Alan Turing, Sur komputeblaj nombroj, kun apliko al la _Entscheidungsproblem_, Paperoj de la Londona Matematika Socio, Serio 2, 42 (1936), _pp_ 230-265. surlinia versio Ĉi tiu estas la _epochal_ papero kie Turing-a difinas Turingaj aŭtomatoj, formulas la problemo de haltado, kaj montras (tiu, ke, kiu) ĝi (kaj ankaŭ la _Entscheidungsproblem_) estas _unsolvable_.
• _Martin_ _Davis_, La Nedecidebla, Baza (Paperoj, Paperas) sur Nedecidebla (Propozicioj, Propozicias), _Unsolvable_ (Problemoj, Problemas) Kaj Komputeblaj Funkcioj, Korvo Premi, (Nov-Jorkio, Novjorko), 1965. Turing-a's papero estas #3 en ĉi tiu volumeno. (Paperoj, Paperas) inkluzivi tiuj per _Godel_, Preĝejo, _Rosser_, Kleene-a, kaj (Afiŝo, Posteno).
• _Martin_ _Davis_, Komputebleco kaj _Unsolvability_, _McGraw_-Monteto, (Nov-Jorkio, Novjorko), 1958.
• Alfreda Nordo _Whitehead_ kaj _Bertrand_ _Russel_, Principoj Mathematica al *56, Kembriĝo (Britio) je la Universitato Premi, 1962. Rao: la problemo de paradoksoj, la (aŭtoroj, aŭtoras) (diskuti, diskuto) la problemo de aro ne esti objekto en (ĉiu, iu) de ĝia "(determinanta, difinanta) funkcioj", en aparta "Enkonduko, Ulo. 1 p. 24 "...(malfacilaĵoj, malfacilaĵas) kiu ekesti en formala logiko", kaj Ulo. 2.Mi. "La Malvirta-Cirkla Principo" p._37ff_, kaj Ulo. 2._VIII_. "La (Kontraŭdiroj, Kontraŭdiras)" p. _60ff_.
• _Martin_ _Davis_, "Kio estas kalkulado", en Matematiko Hodiaŭ, _Lynn_ _Arthur_ _Steen_, Vinberrikolto (Libroj, Mendas) (Hazarda Domo), 1980. Mirinda malgranda papero, eble la plej bona iam skribita pri Turing-a (Maŝinoj, Maŝinas, Aparatoj, Aparatas) por la ne-specialisto. _Davita_ reduktas la Turing-a Maŝino al malproksime-pli simpla modelo bazita sur (Afiŝa, Postena) modelo de kalkulado. Diskutoj _Chaitin_ pruvo. Inkluzivas malgranda (biografioj, biografias) de _Emil_ (Afiŝo, Posteno), Juliino Robinson-a.
• _Marvin_ _Minsky_, Kalkulado, Finia kaj Malfinio (Maŝinoj, Maŝinas, Aparatoj, Aparatas), _Prentice_-Koridoro, _Inc_., N.J., 1967. Vidi ĉapitro 8, Sekcio 8.2 "La _Unsolvability_ de la Haltanta Problemo." Bonega, kio estas legebla, iam amuzado. Klasika.
• _Roger_ _Penrose_, La Imperiestra Nova Menso: Koncernantaj komputiloj, (Mensoj, Mensas, Kapoj, Kapas, Psikoj, Psikas) kaj la Leĝoj de Fiziko, Oksforda Universitato Premi, Oksforda Anglio, 1990 (kun korektadoj). Cf: Ĉapitro 2, "(Algoritmoj, Algoritmas) kaj Turing-a (Maŝinoj, Maŝinas, Aparatoj, Aparatas)". Finite-komplika (surscenigo, prezento) (vidi _Davita_'s papero por pli bona modelo), sed funda (surscenigo, prezento) de Turingaj aŭtomatoj kaj la problemo de haltado, kaj (Eklezia, Kirka, Preĝeja) Λ Kalkulo.
• Johano _Hopcroft_ kaj _Jeffrey_ _Ullman_, Enkonduko al Aŭtomata Teorio, Lingvoj kaj Kalkulado, Addison-a-_Wesley_, Leganta (Maso, Amaso), 1979. Vidi Ĉapitro 7 "Turing-a (Maŝinoj, Maŝinas, Aparatoj, Aparatas)." An libro centrita ĉirkaŭ la maŝino-interpretado de "lingvoj", (Np, NP)-Pleneco, kaj tiel plu
• Andreo _Hodges_, Alan Turing: La _Engima_, _Simon_ kaj _Schuster_, (Nov-Jorkio, Novjorko). Cf Ĉapitro "La (Kuraĝo, Animo, Spirito) de Vero" por historio kondukante al, kaj diskuto de, lia pruvo. Mirinda biografio.
• Bodenlago _Reid_, Hilberto, _Copernicus_: _Springer_-_Verlag_, (Nov-Jorkio, Novjorko), 1996 (unua (publikigita, publikigis) 1970). Fascina historio de Germana matematiko kaj fiziko de 1880's tra 1930's. Centoj de (nomoj, nomas) familiara al (matematikistoj, matematikistas), (fizikistoj, fizikistas) kaj (inĝenieroj, inĝenieras) aperi en ĝiaj paĝoj. Eble _marred_ per ne _overt_ referencoj kaj kelkaj piednotoj: _Reid_ ŝtatoj (ŝia, ŝin) (fontoj, fontas) estita multaj (intervjuoj, intervjuas) kun tiuj kiu persone sciita Hilberto, kaj Hilberta (leteroj, literoj, leteras, literas) kaj (paperoj, paperas).
• Eduardo _Beltrami_, Kio estas Hazarda? Ŝanco kaj (mendi, ordo) en matematiko kaj vivo, _Copernicus_: _Springer_-_Verlag_, (Nov-Jorkio, Novjorko), 1999. Nico, dolĉa legi por la matematike-inklina ne-specialisto, metas _tougher_ remburi je la fino. Havas Turing-a-maŝina modelo en ĝi. Diskutoj la _Chaitin_ (kotizoj, kotizas).
• _Ernest_ _Nagel_ kaj Marmeladoj R. Newman-a, _Godel_’s Pruvo, (Nov-Jorkio, Novjorko) Universitato Premi, 1958. Mirinda skribanta pri tre malfacila subjekto. Por la matematike-inklina ne-specialisto. Diskutoj _Gentzen_'s pruvo sur paĝoj 96-97 kaj piednotoj. _Appendices_ (diskuti, diskuto) la Peana (Aksiomoj, Aksiomas) lakone, singarde prezenti (legiloj, legas) al formala logiko.
• Taylor (Budo, Laŭbo), (Sekvenca (vica, Sinsekva) (Maŝinoj, Maŝinas, Aparatoj, Aparatas) kaj Aŭtomata Teorio, _Wiley_, (Nov-Jorkio, Novjorko), 1967. Cf Ĉapitro 9, Turing-a (Maŝinoj, Maŝinas, Aparatoj, Aparatas). Malfacila libro, intencis por elektra (inĝenieroj, inĝenieras) kaj teknika (specialistoj, specialistas). Diskuta rekursio, parta-rekursio rilate al Turing-a (Maŝinoj, Maŝinas, Aparatoj, Aparatas), problemo de haltado. Havas Turing-a Maŝina modelo en ĝi. Referencoj je fino de Ĉapitro 9 kapti la plejparto de la pli malnova (libroj, mendas) (kio estas 1952 ĝis 1967 inkluzivanta (aŭtoroj, aŭtoras) _Martin_ _Davis_, F. C. _Hennie_, H. Hermeso, S. C. Kleene-a, Sinjoro _Minsky_, T. _Rado_) kaj diversaj teknika (paperoj, paperas). Vidi (tononomo, noto, noti) sub Okupita-Kastoraj Programoj.
• Okupitaj Kastoraj Programoj estas priskribita en Scienca Amerika, Aŭgusto 1984, ankaŭ Marto 1985 p. 23. Referenco en (Budo, Laŭbo) (atribuas, atributoj, atributas) ilin al _Rado_, T.(1962), Sur ne-komputeblaj funkcioj, Sonorilaj Sistemoj _Tech_. J. 41. (Budo, Laŭbo) ankaŭ difinas _Rado_'s Okupita Kastora Problemo en (problemoj, problemas) 3, 4, 5, 6 de Ĉapitro 9, p. 396.
• Davido _Bolter_, Turing-a’s Viro: Okcidenta Kulturo en la Komputila Aĝo, La Universitato de Norda Karolino Premi, Kapela Monteto, 1984. Por la ĝenerala legilo. (Majo, Povas) esti (datita, rendevuita, daktilarbita, daktilujita, daktita). Havas ankoraŭ alia (tre simpla) Turing-a Maŝina modelo en ĝi.