Uzanto:Minjo23/Provejo/Okupata kastoro
En teoria komputoscienco, la ludo okupata kastoro celas trovi finontan programon de antaŭfiksita grandeco kiu (depende de difino) aŭ produktas la plej grandan kvanton da eligo, aŭ daŭre funkcias por la plej longa nombro da paŝoj. Ĉar senfine iteracianta programo produktanta senfinan eligon aŭ funkcianta dum senfina tempo estas facile konceptebla, oni malpermesas tiajn programojn de la ludo. Anstataŭ uzi tradiciajn programlingvojn, la programoj uzataj en la ludo estas n-stataj Turing-maŝinoj, unu el la unuaj matematikaj modeloj de komputado.
Maŝinoj de Turing konsistas el senfina bendo kaj finia aro da ŝtatoj kiuj funkcias kiel la "fontkodo" de la programo. La kvanto da eligo estas difinita kiel la nombro da ciferoj 1 skribitaj sur la bendo, kion oni nomas la poentaro, kaj la daŭro de la programo estas difinita kiel la nombro de paŝoj kiujn ĝi faras antaŭ ol halti. La n-stata ludo okupata kastoro estas trovi la plej longdaŭran aŭ plej alt-poentaran Turing-maŝino kiu havas n statojn kaj iam haltas. Oni premisas ke la maŝinoj estas duumaj (t.e., la bendo povas enhavi nur nulojn kaj unuojn), kaj komencas sur malplena bendo (nur nuloj). Ludanto devas elpensi aron da transiroj inter statoj celante la plej altan poentaron aŭ plej longan daŭron, samtempe certigante ke la maŝino fine haltos.
n-a okupata kastoro, OK-n aŭ simple "okupata kastoro" estas Turing-maŝino kiu gajnas la n-statan ludon okupata kastoro. Depende de difino, ĝi aŭ atingas la plej altan poentaron, aŭ funkcias por la plej longa tempo, inter ĉiuj eblaj n-stataj Turing-maŝinoj. La funkcioj determinantaj la plej altan poentaron aŭ plej longan daŭron de la n-stataj okupataj kastoroj laŭ ĉiu difino estas Σ(n) kaj S(n) respektive.[1]
Decidi la daŭron aŭ poentaron de la n-a okupata kastoro estas nekomputeble. Fakte, kaj la funkcioj Σ(n) kaj S(n) iam fariĝas pli grandaj ol iu ajn komputebla funkcio. Ĉi tio havas implicojn en komputebleca teorio, la problemo de halto, kaj komplikteorio. La koncepto unue enkondukiĝis de Tibor Radó in lia referaĵo de 1962, "Pri Nekomputeblaj Funkcioj".[1]
Referencoj
[redakti | redakti fonton]- ↑ 1,0 1,1 (May 1962) “On non-computable functions”, Bell System Technical Journal 41 (3), p. 877–884. doi:10.1002/j.1538-7305.1962.tb00480.x.