väsi(n, m) väsi(n ∈ ℕ, m ∈ ℕ) ∈ ℕ
while n ≥ m do
   n := n − m
return n ξ_n(σ) ξ_n(σ ∈ Σ*) ∈ ℕ
j := 0
if apt(σ, σ, n) then
   for i := 1 to n do
      j := j + 1
return j

Teh­tä­vä:
Li­sää py­säh­ty­mi­sen tes­taa­mi­ses­ta

Ly­hyt Math­Check-oh­je (uu­teen vä­li­leh­teen)

Tä­mä teh­tä­vä on jat­koa teh­tä­väl­le Py­säh­ty­mis­tes­te­rin mah­dot­to­muus. Täs­sä teh­tä­väs­sä käy­te­tään siel­lä esi­tel­ty­jä kä­sit­tei­tä ja mer­kin­tö­jä, jo­ten se pi­tää teh­dä en­sin.

1. Ali­oh­jel­man suo­rit­ta­mien as­kel­ten mää­rä
2. As­kel­ra­joi­te­tun py­säh­ty­mi­sen tes­te­ri
3. Jo­kai­nen as­kel­ra­joi­te­tun py­säh­ty­mi­sen tes­te­ri on toi­si­naan hi­das
4. Tyh­jän syöt­teen py­säh­ty­mis­tes­te­riä ei ole
5. Lo­puk­si

Ali­oh­jel­man suo­rit­ta­mien as­kel­ten mää­rä

Ali­oh­jel­man suo­rit­ta­mi­seen ku­lu­va ai­ka riip­puu pait­si ali­oh­jel­mas­ta ja sen syöt­tees­tä, myös tie­to­ko­nees­ta jos­sa ali­oh­jel­ma aje­taan, kään­tä­jäs­tä jol­la ali­oh­jel­ma kään­net­tiin tai tul­kis­ta jol­la si­tä tul­ka­taan, sii­tä mi­tä muu­ta sa­ma tie­to­ko­ne te­kee sa­man­ai­kai­ses­ti ja niin edel­leen. Toi­saal­ta isoil­la syöt­teil­lä ku­lu­va ai­ka ei usein­kaan rii­pu en­si­si­jai­ses­ti näis­tä, vaan ali­oh­jel­mas­sa käy­tet­ty­jen al­go­rit­mien va­lin­nas­ta. Tark­ka ajan­käy­tön ana­lyy­si on siis se­kä hy­vin vai­keaa et­tä mel­ko tar­pee­ton­ta. Sik­si tie­to­jen­kä­sit­te­ly­tie­tees­sä tut­ki­taan har­voin tark­kaa ajan­ku­lu­tus­ta. Sen si­jaan ajan­ku­lu­tus­ta ar­vioi­daan niin sa­no­tuil­la O-, Θ- ja Ω-mer­kin­nöil­lä.

O- yms. mer­kin­nät ovat va­li­tet­ta­vas­ti jos­sain mää­rin vai­kea­ta­jui­sia, jo­ten em­me käy­tä nii­tä täs­sä teh­tä­väs­sä. Sen si­jaan ku­vit­te­lem­me ali­oh­jel­man suo­ri­tuk­sen koos­tu­van as­ke­lis­ta ja las­kem­me as­kel­ten mää­riä. O- yms. mer­kin­tö­jen mie­les­sä oi­kei­den tu­los­ten saa­mi­sek­si riit­tää, et­tä yh­den as­ke­leen suo­rit­ta­mi­seen ku­lu­val­la ajal­la on syöt­tees­tä riip­pu­ma­ton po­si­tii­vi­nen ala­ra­ja ja syöt­tees­tä riip­pu­ma­ton po­si­tii­vi­nen ylä­ra­ja. As­ke­leen suo­ri­tus­ai­ka saa siis vaih­del­la, mut­ta ei mi­ten pal­jon ta­han­sa. Esi­mer­kik­si tau­lu­kon nol­laa­mi­nen vaa­tii mon­ta as­kel­ta, kos­ka sen ku­lut­ta­ma ai­ka kas­vaa ra­jat­ta tau­lu­kon koon kas­vaes­sa.

Mi­kä tark­kaan ot­taen muo­dos­taa as­ke­leen ei siis ole olen­nais­ta. Päät­te­lyi­den ym­mär­tä­mi­sen hel­pot­ta­mi­sek­si so­vim­me kui­ten­kin, et­tä ku­kin seu­raa­vis­ta vie yh­den as­ke­leen:

• yk­sit­täi­nen las­ku­toi­mi­tus (esi­mer­kik­si yh­teen­las­ku tai ja­ko­las­ku),
• muut­tu­jaan si­joit­ta­mi­nen,
• muut­tu­jan ar­von tes­taa­mi­nen va­kio­ta tai muut­tu­jaa vas­taan,
• ali­oh­jel­mas­ta pa­luu, se­kä
• for-sil­mu­kan sil­muk­ka­muut­tu­jan ar­von kas­vat­ta­mi­nen yh­del­lä.

Siir­ty­mi­nen tes­ti­tu­lok­sen pe­rus­teel­la toi­seen paik­kaan ali­oh­jel­maa ei vie yh­tään as­kel­ta (riit­tää, et­tä tes­tin suo­rit­ta­mi­nen vie). Pa­luu sil­mu­kan al­kuun ei vie yh­tään as­kel­ta (riit­tää, et­tä sil­muk­ka­eh­don tes­taa­mi­nen vie). Jos ali­oh­jel­man suo­ri­tus ei py­säh­dy, niin se suo­rit­taa lo­put­to­mas­ti as­ke­lia, ja päin­vas­toin. ”Ää­ret­tö­män mon­ta as­kel­ta” tar­koit­taa sa­maa kuin ”lo­put­to­mas­ti as­ke­lia”.

Seu­raa­van ali­oh­jel­man suo­rit­ta­mien as­kel­ten mää­rä n:n funk­tio­na on ok_text Oi­kein! /*Sil­mu­kan jo­kai­sel­la kier­rok­sel­la teh­dään 4 as­kel­ta: #<br#>1. To­de­taan, et­tä #<i#>i#</i#> ≤ #<i#>n#</i#> ja men­nään sil­mu­kan var­ta­loon. #<br#>2. Las­ke­taan #<i#>j#</i#> + #<i#>i#</i#>. #<br#>3. Si­joi­te­taan edel­li­sen koh­dan tu­los #<i#>j#</i#>:hin. #<br#>4. Kas­va­te­taan #<i#>i#</i#>:tä ja pa­la­taan sil­mu­kan al­kuun. #<br#>Li­säk­si alus­sa nol­la­taan #<i#>j#</i#>; ker­ran to­de­taan et­tä #<i#>i#</i#> ≤ #<i#>n#</i#> ei pä­de ja tul­laan pois sil­mu­kas­ta; ja suo­ri­te­taan #<b#>return#</b#> #<i#>j#</i#>.*/ f_nodes 5 hide_expr 4n+3 =
tai

esimerkki1(n ∈ ℕ) ∈ ℕ
j := 0
for i := 1 to n do
   j := j + i
return j

Seu­raa­val­la ali­oh­jel­mal­la ei ole syö­tet­tä. Ali­oh­jel­mas­ta nä­kee he­ti, et­tä sen suo­rit­ta­mien as­kel­ten mää­rä on …ää­re­tön. Suo­ri­tus juut­tuu ikui­seen sil­muk­kaan ei­kä pää­se kos­kaan return-lau­see­seen. Niin­pä ali­oh­jel­ma suo­rit­taa ää­ret­tö­män mon­ta as­kel­ta.

esimerkki2 ∈ ℕ
i := 0
while T do
   i := i + 1
return i

Lo­pul­li­set tu­lok­set il­mai­sem­me muo­dos­sa, jo­ka ei rii­pu as­ke­liin ja­ka­mi­sen yk­si­tyis­koh­dis­ta ei­kä sii­tä, kuin­ka pal­jon ai­kaa yh­den as­ke­leen suo­rit­ta­mi­nen vie. Käy­täm­me muun muas­sa il­maus­ta n:n suh­teen li­neaa­ri­nen. Voit aja­tel­la, et­tä se tar­koit­taa ”suu­rin piir­tein yh­tä­suu­ri kuin n”. Esi­mer­kik­si se­kä 4n + 1000000 et­tä n − 1000000 ovat n:n suh­teen li­neaa­ri­sia. Ha­lu­tes­sa­si voit lu­kea tar­kan mää­ri­tel­män täs­täAs­kel­mää­rä on enin­tään n:n suh­teen li­neaa­ri­nen, jos ja vain jos sil­le on ole­mas­sa ylä­ra­ja muo­toa an + b, mis­sä a on po­si­tii­vi­nen reaa­li­lu­ku ja b on reaa­li­lu­ku. Il­maus O(n) tar­koit­taa sa­maa.

As­kel­mää­rä on vä­hin­tään n:n suh­teen li­neaa­ri­nen, jos ja vain jos sil­le on ole­mas­sa ala­ra­ja muo­toa an + b, mis­sä a on po­si­tii­vi­nen reaa­li­lu­ku ja b on reaa­li­lu­ku. Il­maus Ω(n) tar­koit­taa sa­maa.

As­kel­mää­rä on n:n suh­teen li­neaa­ri­nen, jos ja vain jos se on se­kä vä­hin­tään et­tä enin­tään n:n suh­teen li­neaa­ri­nen. Il­maus Θ(n) tar­koit­taa sa­maa..

Käy­täm­me seu­raa­vaa ali­oh­jel­maa jat­kos­sa pal­jon esi­merk­ki­nä. Se löy­tyy myös oi­keal­ta pa­lau­te­laa­ti­kon ylä­puo­lel­ta. Ni­mi väsi tu­lee sa­nas­ta ”vä­hen­nys­sil­muk­ka”.

väsi(n ∈ ℕ, m ∈ ℕ) ∈ ℕ
while n ≥ m do
   n := n − m
return n

Kuin­ka mon­ta as­kel­ta väsi(12, 5):n suo­ri­tus vie? vas­tausKah­dek­san:
1. To­de­taan, et­tä 12 ≥ 5 ja men­nään sil­mu­kan var­ta­loon.
2. Las­ke­taan 12 − 5 ja saa­daan 7.
3. Si­joi­te­taan 7 n:ään.
4. To­de­taan, et­tä 7 ≥ 5 ja men­nään sil­mu­kan var­ta­loon.
5. Las­ke­taan 7 − 5 ja saa­daan 2.
6. Si­joi­te­taan 2 n:ään.
7. To­de­taan, et­tä 2 < 5 ja men­nään pois sil­mu­kas­ta.
8. Pa­lau­te­taan 2.

Kuin­ka mon­ta as­kel­ta väsi(12, 0):n suo­ri­tus vie? vas­tausÄä­ret­tö­män mon­ta. Kos­ka m = 0, ei n:n ar­vo muu­tu si­joi­tuk­ses­sa n := n − m. Sik­si ali­oh­jel­man sil­muk­kaa suo­ri­te­taan ikui­ses­ti.

Kuin­ka mon­ta as­kel­ta väsi(1002, 5):n suo­ri­tus vie? vih­jeJos n ≥ 5, niin kol­me seu­raa­vaa as­kel­ta pie­nen­tää n:ää vii­del­lä. Niin­pä 600 as­kel­ta pie­nen­tää n:ää tu­han­nel­la. Sen jäl­keen n < 5, jol­loin suo­ri­te­taan enää kak­si as­kel­ta: sil­mu­kas­ta pois­tu­mi­nen ja return n. vas­taus602

Kuin­ka mon­ta as­kel­ta väsi(1000002, 5):n suo­ri­tus vie? vas­taus600002

Kuin­ka mon­ta as­kel­ta väsi(n, 1):n suo­ri­tus vie? ok_text Oi­kein! f_nodes 5 hide_expr 3n+2 =
tai

Teh­tä­vä eri­kois­osaa­jil­le: kuin­ka mon­ta as­kel­ta väsi(n, m):n suo­ri­tus vie, jos m > 0? ok_text Oi­kein! f_nodes 8 hide_expr 3(n div m)+2 =
tai

Seu­raa­va ali­oh­jel­ma ha­vain­nol­lis­taa, et­tä jos­kus ei ole help­po sel­vit­tää, kuin­ka mon­ta as­kel­ta ali­oh­jel­man suo­rit­ta­mi­nen vie. Se on ni­met­ty on­gel­maa tut­ki­neen ma­te­maa­ti­kon mu­kaan. Teh­tä­vän hel­pot­ta­mi­sek­si em­me täl­lä ker­taa las­ke as­ke­lia vaan while-sil­mu­kan kier­rok­sia. Kuin­ka mon­ta kier­ros­ta se te­kee, jos alus­sa
n =  7? only_no_yes_on ok_text Oi­kein! /*#<i#>n#</i#> saa 7:n jäl­keen ar­vot 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1*/ f_nodes 1 hide_expr 16= tai

n = 85? only_no_yes_on ok_text Oi­kein! /*#<i#>n#</i#> saa 85:n jäl­keen ar­vot 256, 128, 64, 32, 16, 8, 4, 2, 1*/ f_nodes 1 hide_expr 9= tai

n = 27? only_no_yes_on ok_text Oi­kein! fail_text Voit vaik­ka teh­dä an­ne­tun pseu­do­koo­din poh­jal­ta pik­ku oh­jel­man, li­sä­tä sii­hen as­kel­ten las­ken­nan ja ajaa sen. f_nodes 1 hide_expr 111= tai

Collatz(n ∈ ℕ) ∈ ℕ
while n > 1 do
   if n on pa­ril­li­nen then
      n :=

n

2

   else
      n := 3n + 1
return n

Jos kaik­ki ali­oh­jel­mat py­säh­tyi­si­vät ai­na lo­pul­ta kai­kil­la syöt­teil­lä, niin as­kel­ten mää­rä saa­tai­siin ai­na sel­vil­le suo­rit­ta­mal­la ali­oh­jel­ma ja las­ke­mal­la as­ke­leet. Mut­ta, ku­ten to­te­sim­me edel­lä, esi­mer­kik­si väsi(12, 0) ei py­säh­dy. Jos em­me tun­ne ali­oh­jel­man koo­dia, niin vaik­ka ali­oh­jel­man suo­ri­tus oli­si jo kes­tä­nyt hy­vin kauan, em­me voi ju­lis­taa et­tä se on ikui­ses­sa sil­mu­kas­sa, sil­lä voi­han ol­la et­tä se lo­pet­tai­si jos malt­tai­sim­me odot­taa vie­lä jon­kin ai­kaa. Jos oli­si ole­mas­sa yleis­pä­te­vä kei­no saa­da vas­taus ky­sy­myk­seen ”kuin­ka mon­ta as­kel­ta an­ne­tun ali­oh­jel­man suo­ri­tus vie an­ne­tul­la syöt­teel­lä”, niin si­tä voi­tai­siin käyt­tää py­säh­ty­mis­tes­te­ri­nä: jos kei­no an­taa vas­tauk­sek­si luon­nol­li­sen lu­vun, niin tut­kit­tu ali­oh­jel­ma py­säh­tyy, ja jos kei­no vas­taa ”ää­re­tön”, niin tut­kit­tu ali­oh­jel­ma ei py­säh­dy.

Ym­mär­tääk­sem­me pa­rem­min mis­tä on ky­se, tut­kim­me koh­ta ky­sy­mys­tä, jo­hon voi­daan ai­na saa­da vas­taus ää­rel­li­ses­sä ajas­sa: py­säh­tyy­kö an­net­tu ali­oh­jel­ma an­ne­tul­la syöt­teel­lä suo­ri­tet­tuaan enin­tään an­ne­tun mää­rän as­ke­lia. Tä­mä ky­sy­mys on kyl­lä/ei-ky­sy­mys. Sii­hen voi­daan saa­da vas­taus suo­rit­ta­mal­la ali­oh­jel­maa kun­nes se py­säh­tyy tai an­net­tu mää­rä as­ke­lia tu­lee täy­teen.

Jos tie­de­tään, et­tä ali­oh­jel­man suo­rit­ta­mien as­kel­ten mää­rä on k, mis­sä k on luon­nol­li­nen lu­ku tai ää­re­tön, niin täl­lä ta­val­laif k = ää­re­tön then
   return F
else if k ≤ n then
   return T
else
   return F voi­daan sel­vit­tää, py­säh­tyy­kö ali­oh­jel­ma enin­tään n as­ke­leel­la.

Teo­rian ke­hit­tä­mi­sen hel­pot­ta­mi­sek­si tar­kas­te­lem­me vain ali­oh­jel­mia, joi­den syö­te koos­tuu yh­des­tä osas­ta ja se osa on merk­ki­jo­no. Tä­mä ei vä­hen­nä tu­los­ten yleis­pä­te­vyyt­tä, kos­ka muun­lai­sel­le syöt­teel­le voi­daan so­pia jo­kin esi­tys­ta­pa merk­ki­jo­no­na, ja ali­oh­jel­man eteen voi­daan li­sä­tä vai­he, jo­ka tul­kit­see tä­män merk­ki­jo­non al­ku­pe­räi­sen ali­oh­jel­man ha­lua­mak­si syöt­teek­si. Merk­ki­jo­no­va­kiot esi­te­tään ”kak­sin­ker­tai­sis­sa” ja merk­ki­va­kiot ku­ten ’x’ yk­sin­ker­tai­sis­sa lai­naus­mer­keis­sä.

väsi_mj(σ ∈ Σ*) ∈ ℕ
li­sää σ:n lop­puun '.'    // var­mis­taa, et­tei suo­ri­tus kaa­du
n := 0;  m := 0;  i := 1
while '0' ≤ σ[i] ≤ '9' do
   n := 10n + σ[i] − '0';  i := i + 1
while σ[i] = ' ' do
   i := i + 1
while '0' ≤ σ[i] ≤ '9' do
   m := 10m + σ[i] − '0';  i := i + 1
while n ≥ m do
   n := n − m
return n

Mi­tä tä­mä esi­merk­ki olet­taa merk­ki­jo­no­jen in­dek­soin­nis­ta? vas­tausSe olet­taa, et­tä ne in­dek­soi­daan yk­kö­ses­tä al­kaen. Tä­mä nä­kyy sii­tä, et­tä väsi_mj se­laa σ:aa koh­das­ta 1 al­kaen. Se mah­dol­li­suus, et­tä in­dek­soin­ti al­kai­si nol­las­ta mut­ta σ[0] jä­te­tään käyt­tä­mät­tä, on sul­jet­tu pois täl­lä pe­rus­teel­laväsi_mj(ε) tut­kii σ[1]:n kun σ = ”.”. Se on lail­lis­ta vain jos in­dek­soin­ti al­kaa yk­kö­ses­tä.

Jos in­dek­soin­ti al­kaa yk­kö­ses­tä, niin väsi_mj(σ) in­dek­soi σ:aa vain lail­li­ses­ti seu­raa­vas­ta syys­tä. Se in­dek­soi en­sim­mäi­ses­tä koh­das­ta al­kaen kor­kein­taan niin pit­käl­le kun­nes löy­tyy ’.’. Se löy­tyy var­mas­ti, kos­ka σ:n lo­pus­sa on ’.’..

Ole­tam­me, et­tä väsi_mj:n en­sim­mäi­nen while-sil­muk­ka vie 8 as­kel­ta kier­ros­ta koh­ti, sa­moin kol­mas, toi­nen vie 3 as­kel­ta kier­ros­ta koh­ti, sa­moin nel­jäs, ja muu­hun me­nee 12 as­kel­ta. (Lu­vuis­sa ole­te­taan, et­tä in­dek­soin­ti σ[i] vie as­ke­leen sil­mu­kan eh­dos­sa mut­ta ei sil­mu­kan var­ta­los­sa, kos­ka siel­lä voi­daan käyt­tää eh­dos­sa jo saa­tua tu­los­ta.) Kuin­ka mon­ta as­kel­ta seu­raa­vien kut­su­jen suo­ri­tus vie?

väsi_mj(  ”1 1”)? only_no_yes_on ok_text Oi­kein! /*1. sil­muk­ka: 8 (lue­taan yk­si nu­me­ro­merk­ki)#<br#> 2. sil­muk­ka: 3 (lue­taan yk­si vä­li­lyön­ti)#<br#> 3. sil­muk­ka: 8 (lue­taan yk­si nu­me­ro­merk­ki)#<br#> 4. sil­muk­ka: 3 (yk­si kier­ros, jos­sa #<i#>n#</i#> pie­ne­nee 1:stä 0:aan)#<br#> muu: 12*/ f_nodes 1 hide_expr 34 = tai

väsi_mj( ”10 1”)? only_no_yes_on ok_text Oi­kein! /*1. sil­muk­ka: 16 (lue­taan kak­si nu­me­ro­merk­kiä)#<br#> 2. sil­muk­ka: 3 (lue­taan yk­si vä­li­lyön­ti)#<br#> 3. sil­muk­ka: 8 (lue­taan yk­si nu­me­ro­merk­ki)#<br#> 4. sil­muk­ka: 30 (10 kier­ros­ta, jois­sa #<i#>n#</i#> pie­ne­nee 10:stä 0:aan)#<br#> muu: 12*/ f_nodes 1 hide_expr 69 = tai

väsi_mj(”100 1”)? only_no_yes_on ok_text Oi­kein! /*1. sil­muk­ka: 24 (lue­taan kol­me nu­me­ro­merk­kiä)#<br#> 2. sil­muk­ka: 3 (lue­taan yk­si vä­li­lyön­ti)#<br#> 3. sil­muk­ka: 8 (lue­taan yk­si nu­me­ro­merk­ki)#<br#> 4. sil­muk­ka: 300 (100 kier­ros­ta, jois­sa #<i#>n#</i#> pie­ne­nee 100:stä 0:aan)#<br#> muu: 12*/ f_nodes 1 hide_expr 347 = tai

väsi_mj(σ_k), mis­sä σ_k:ssa on en­sin yk­kö­nen, sit­ten k kap­pa­let­ta nol­lia, sit­ten vä­li­lyön­ti, ja lo­puk­si yk­kö­nen?
ok_text Oi­kein! /*1. sil­muk­ka: 8#<i#>k#</i#> + 8 (lue­taan #<i#>k#</i#> + 1 nu­me­ro­merk­kiä)#<br#> 2. sil­muk­ka: 3 (lue­taan yk­si vä­li­lyön­ti)#<br#> 3. sil­muk­ka: 8 (lue­taan yk­si nu­me­ro­merk­ki)#<br#> 4. sil­muk­ka: 3 ⋅ 10#<sup#>#<i#>k#</i#>#</sup#> (10#<sup#>#<i#>k#</i#>#</sup#> kier­ros­ta, jois­sa #<i#>n#</i#> pie­ne­nee 0:aan)#<br#> muu: 12*/ f_nodes 11 hide_expr 3*10^k + 8k + 31 = tai

Täs­sä esi­mer­kis­sä syö­te on merk­ki­jo­no, jon­ka pi­tuus on k + 3. Jos syöt­teen pi­tuut­ta mer­ki­tään s:llä, niin as­kel­ten mää­rä on 3 ⋅ 10^s−3 + 8s + 7. Tä­män ver­taa­mi­nen teh­tä­vän ”Kuin­ka mon­ta as­kel­ta väsi(n, 1):n suo­ri­tus vie?” vas­tauk­seen3n + 2 ha­vain­nol­lis­taa si­tä, et­tä on ai­van eri asia mi­ta­ta suo­ri­tus­ai­kaa syöt­teen pi­tuu­den funk­tio­na kuin syöt­tees­sä esiin­ty­vän lu­vun lu­ku­ar­von funk­tio­na.

As­kel­ra­joi­te­tun py­säh­ty­mi­sen tes­te­ri

Tar­vit­sem­me tois­tu­vas­ti il­maus­ta ”ali­oh­jel­ma, jon­ka syö­te on yk­si merk­ki­jo­no”, jo­ten ly­hen­näm­me sen ajsoym.

Suo­ri­tuk­seen pe­rus­tu­va as­kel­ra­joi­te­tun py­säh­ty­mi­sen tes­te­ri on ali­oh­jel­ma spapt(π, σ, n), jol­la on seu­raa­vat omi­nai­suu­det. En­sin se tut­kii, on­ko π ajsoym. Jol­lei ole, niin spapt(π, σ, n) = F eli spapt(π, σ, n) pa­laut­taa F. Jos on, niin se suo­rit­taa π:tä σ:lla kun­nes se py­säh­tyy tai n suo­ri­tus­as­kel­ta tu­lee täy­teen. Jos suo­ri­tus py­säh­tyi, niin spapt(π, σ, n) = T. Jos se ei py­säh­ty­nyt, niin spapt(π, σ, n) = F.

only_no_yes_on ok_text Oi­kein! fail_text Osat ovat π, σ ja #<i#>n#</i#>. f_nodes 1 hide_expr 3 = Ali­oh­jel­man spapt syöt­tees­sä on osaa. end_of_answer fail_text Suo­ri­te­taan π(σ):aa. f_nodes 1 hide_expr 1 = Nii­den tyy­pit ovat vas­tausmerk­ki­jo­no, merk­ki­jo­no ja luon­nol­li­nen lu­ku. Jos π on ajsoym, niin π:n syöt­tees­sä on osaa. Nii­den tyy­pit ovat vas­tausmerk­ki­jo­no. Ali­oh­jel­man spapt tu­lok­sen tyyp­pi on vas­tausto­tuus­ar­vo.
tai

Jos π(σ) ei py­säh­dy ja n = 73, niin mi­tä on spapt(π, σ, n)? vas­tausSe on F. Kos­ka π(σ):n suo­ri­tus jat­kuu lo­put­to­mas­ti, se ei py­säh­dy 73 as­ke­lee­seen men­nes­sä.

Suo­ri­tuk­seen pe­rus­tu­va as­kel­ra­joi­te­tun py­säh­ty­mi­sen tes­te­ri voi­daan to­teut­taa. Oh­jel­moin­ti­kiel­ten kään­tä­jiä osa­taan teh­dä, ei­kä spapt(π, σ, n) poik­kea niis­tä pal­jon­kaan. Sen tut­ki­mi­nen, on­ko π ajsoym, on ta­val­lis­ta kään­tä­jä­tek­niik­kaa ja saa­daan on­nis­tu­maan jo­kai­sel­la π. Tut­ki­mi­nen ei siis jää ikui­seen sil­muk­kaan mil­lään π. Kään­nök­ses­sä voi­daan π:n suo­ri­tuk­sen lo­pun ti­lal­le lait­taa return true ja jo­kai­nen π:n as­kel voi­daan kor­va­ta seu­raa­val­la:

if n > 0 then
   n := n − 1
   suo­ri­ta π(σ):n as­kel
else
   return F

Mis­sä ta­pauk­ses­sa spapt(π, σ, n) jää ikui­seen sil­muk­kaan? vas­tausEi mis­sään. Edel­lä lu­vat­tiin, et­tä π:n tut­ki­mi­nen ei voi jää­dä ikui­seen sil­muk­kaan ja π(σ):n yh­den as­ke­leen suo­ri­tus vie ää­rel­li­sen mää­rän spapt(π, σ, n):n as­ke­lia. Jos π(σ):n suo­ri­tus ei lo­pu kos­kaan, niin spapt(π, σ, n) jät­tää π(σ):n suo­rit­ta­mi­sen kes­ken n:n as­ke­leen jäl­keen, jo­ten täs­sä­kään vai­hees­sa spapt(π, σ, n) ei voi jää­dä ikui­seen sil­muk­kaan.

Yh­den π(σ):n as­ke­leen suo­rit­ta­mi­nen vie nel­jä as­kel­ta, jot­ka ovat nä­mä 1. tes­ti n > 0 ja sen pe­rus­teel­la then-haa­raan me­no
2. ar­von n − 1 las­ke­mi­nen
3. edel­lä saa­dun ar­von si­joit­ta­mi­nen n:ään
4. π(σ):n as­ke­leen suo­rit­ta­mi­nen. Lu­ku 4 ei ole yleis­pä­te­vä vaan on va­lit­tu konk­re­tian vuok­si, ku­ten edel­lä to­det­tiin. Yleis­pä­te­vää on, et­tä

• Yh­den π(σ):n as­ke­leen suo­rit­ta­mi­nen vie ai­na­kin yh­den mut­ta vain ää­rel­li­sen, n:stä riip­pu­mat­to­man mää­rän spapt(π, σ, n):n as­ke­lia.
• spapt(π, σ, n):n suo­rit­ta­mien as­kel­ten mää­rä on enin­tään li­neaa­ri­nen n:n suh­teen. Pe­rus­te­lu: Ol­koon a nii­den as­kel­ten mää­rä, jot­ka spapt(π, σ, n) käyt­tää yh­den π(σ):n as­ke­leen suo­rit­ta­mi­seen. Ol­koon b nii­den as­kel­ten mää­rä, jot­ka spapt(π, σ, n) enin­tään käyt­tää π:n tut­ki­mi­seen, π(σ):n suo­rit­ta­mi­sen käyn­nis­tä­mi­seen tai ohit­ta­mi­seen se­kä lop­pu­toi­men­pi­tei­siin­sä. spapt(π, σ, n) käyt­tää π(σ):n suo­rit­ta­mi­seen enin­tään ok_text Oi­kein! fail_text Vas­tauk­sen pi­tää käyt­tää #<i#>a#</i#>:ta, #<i#>b#</i#>:tä ja/tai #<i#>n#</i#>:ää. Ei voi kor­va­ta #<i#>a#</i#> = 4, kos­ka se ei ole yleis­pä­te­vää. f_nodes 3 hide_expr a n = as­kel­ta ja kaik­kiaan enin­tään end_of_answer arithmetic f_nodes 5 hide_expr a n + b = as­kel­ta.
  tai
• Jos π on ajsoym ja π(σ) ei py­säh­dy n as­ke­lees­sa, niin spapt(π, σ, n) suo­rit­taa enem­män kuin n as­kel­ta täs­tä syys­täSe suo­rit­taa n kap­pa­let­ta π(σ):n as­ke­lia. Yh­den π(σ):n as­ke­leen suo­rit­ta­mi­nen vie ai­na­kin yh­den spapt(π, σ, n):n as­ke­leen. Nii­tä en­nen se tut­ki π:n, mi­hin me­ni enem­män kuin nol­la as­kel­ta..

Jäl­kim­mäi­nen pom­pu­la tar­koit­taa, et­tä hi­taim­mil­laan spapt(π, σ, n) käyt­tää enem­män as­ke­lia kuin ali­oh­jel­man π suo­rit­ta­mi­nen syöt­teel­lä σ enin­tään n as­kel­ta vei­si, sii­tä yk­sin­ker­tai­ses­ta syys­tä, et­tä täl­löin spapt(π, σ, n) suo­rit­taa ali­oh­jel­man π syöt­teel­lä σ enin­tään n as­kel­ta ja te­kee jo­tain muu­ta­kin. Ai­kai­sem­min oli esi­merk­ke­jä, jois­sa ali­oh­jel­man suo­rit­ta­mien as­kel­ten mää­rä saa­tiin sel­vil­le ih­mis­jär­keä käyt­tä­mäl­lä pal­jon pie­nem­mäl­lä työ­mää­räl­lä kuin ali­oh­jel­man suo­rit­ta­mi­nen oli­si ih­mi­sel­tä vie­nyt. Jos sait las­ket­tua, et­tä väsi(1000002, 5):n suo­rit­ta­mi­nen vie 600 002 as­kel­ta, niin tus­kin­pa teit si­tä suo­rit­ta­mal­la kaik­ki yli kuu­si­sa­taa­tu­hat­ta as­kel­ta mie­les­sä­si tai ky­näl­lä ja pa­pe­ril­la.

Vaik­ka edel­lä ol­leis­sa esi­mer­keis­sä päät­te­li­jä­nä oli ih­mi­nen, niis­sä käy­tet­ty­jä kik­ko­ja voi­si to­teut­taa myös ali­oh­jel­mi­na. Niit­ten avul­la voi­tai­siin to­teut­taa tes­te­ri, jo­ka tuot­tai­si ai­na sa­man vas­tauk­sen kuin spapt(π, σ, n), mut­ta oli­si ai­na­kin joil­la­kin π, σ ja n pal­jon no­peam­pi ei­kä kos­kaan olen­nai­ses­ti hi­taam­pi. Tes­te­ri tes­tai­si, ovat­ko π ja σ ki­kan edel­lyt­tä­mää muo­toa. Jos ei­vät ole, tes­te­ri toi­mi­si ku­ten spapt(π, σ, n).

Ki­kat toi­mi­vat kui­ten­kin vain joil­le­kin π ja σ. Seu­raa­vak­si tut­kim­me, on­ko ole­mas­sa kai­kil­le π ja σ toi­mi­vaa me­ne­tel­mää, jol­la vas­taus ky­sy­myk­seen ”py­säh­tyy­kö π(σ) vii­meis­tään n:n as­ke­leen jäl­keen” saa­daan ai­na no­peas­ti. Si­tä var­ten an­nam­me ni­men pal­ve­lul­le, jon­ka spapt(π, σ, n) tuot­taa, il­man et­tä ra­joi­tam­me mil­lään ta­val­la si­tä, mi­ten se to­teu­te­taan.

Mää­ri­tel­mä As­kel­ra­joi­te­tun py­säh­ty­mi­sen tes­te­ri on mi­kä ta­han­sa ali­oh­jel­ma apt(π, σ, n), jol­la on seu­raa­vat omi­nai­suu­det. Jos π:n si­säl­tö on ali­oh­jel­ma, jon­ka syö­te on yk­si merk­ki­jo­no ja jo­ka py­säh­tyy vii­meis­tään n as­ke­leel­la syöt­teel­lä σ, niin apt(π, σ, n) = T. Muus­sa ta­pauk­ses­sa apt(π, σ, n) = F.

Voi­ko apt(π, σ, n) jää­dä ikui­seen sil­muk­kaan? vas­tausEi voi. Tä­mä lu­vat­tiin sa­no­mal­la, et­tä jos apt(π, σ, n) ei ole T, niin se on F. apt(π, σ, n) ei siis kos­kaan jä­tä tuot­ta­mat­ta vas­taus­ta.

Kos­ka spapt(π, σ, n) on as­kel­ra­joi­te­tun py­säh­ty­mi­sen tes­te­ri ja sen as­kel­mää­rä to­det­tiin edel­lä enin­tään li­neaa­ri­sek­si n:n suh­teen, seu­raa­va väi­te pä­tee:

Lau­se 1 As­kel­ra­joi­te­tun py­säh­ty­mi­sen tes­te­ri on ole­mas­sa. Suo­ri­tus­ajal­taan enin­tään n:n suh­teen li­neaa­ri­nen as­kel­ra­joi­te­tun py­säh­ty­mi­sen tes­te­ri on ole­mas­sa.

Jo­kai­nen as­kel­ra­joi­te­tun py­säh­ty­mi­sen tes­te­ri on toi­si­naan hi­das

Edel­lä to­te­sim­me, et­tä jos π(σ) ei py­säh­dy vii­meis­tään n:llä as­ke­leel­la, spapt(π, σ, n):ltä me­nee enem­män kuin n as­kel­ta to­de­ta tä­mä. Myös to­te­sim­me, et­tä joil­le­kin π ja σ tä­mä voi­daan teh­dä pal­jon no­peam­min et­si­mäl­lä vas­taus muul­la ta­val­la kuin mi­ten spapt(π, σ, n) toi­mii. Seu­raa­vak­si osoi­tam­me, et­tä ei ole ole­mas­sa kik­kaa, jol­la kai­kil­la π ja σ tu­los saa­daan pal­jon no­peam­min. Va­li­taan mi­kä as­kel­ra­joi­te­tun py­säh­ty­mi­sen tes­te­ri ta­han­sa, on ole­mas­sa ali­oh­jel­mia ja syöt­tei­tä, joil­le tes­te­rin suo­rit­ta­mi­nen kes­tää mel­kein yh­tä kauan kuin ali­oh­jel­man suo­ri­tus kes­täi­si. Väit­teen tark­ka muo­toi­lu on seu­raa­va:

Lau­se 2 On ole­mas­sa sel­lai­nen va­kio b ∈ ℕ, et­tä jo­kai­sel­le as­kel­ra­joi­te­tun py­säh­ty­mi­sen tes­te­ril­le apt ja jo­kai­sel­le n ∈ ℕ on ole­mas­sa sel­lai­nen π, et­tä apt(π, π, n):n suo­ri­tus vie ai­na­kin n − b as­kel­ta.

To­dis­tam­me väit­teen laa­ti­mal­la ti­lan­teen, jos­sa ali­oh­jel­man suo­ri­tus pyy­tää apt:ia ker­to­maan oman tu­le­vai­suu­ten­sa eli mi­tä suo­ri­tus it­se tu­lee te­ke­mään. Ali­oh­jel­man syöt­tee­nä on siis ali­oh­jel­ma it­se. Jos apt vas­taa, et­tä suo­ri­tus tu­lee vie­mään enin­tään n as­kel­ta, niin ali­oh­jel­ma jat­kaa suo­rit­ta­mal­la sil­mu­kan jo­ka vie enem­män kuin n as­kel­ta. Si­ten ali­oh­jel­ma huo­leh­tii, et­tä tä­mä vas­taus on vää­rin. Jos apt vas­taa, et­tä suo­ri­tus tu­lee vie­mään enem­män kuin n as­kel­ta, niin ali­oh­jel­ma lo­pet­taa niin no­peas­ti kuin pys­tyy.

Kos­ka py­säh­ty­mis­tes­te­ri ei ole py­säh­ty­mis­tes­te­ri el­lei se vas­taa ai­na oi­kein, ai­noa mah­dol­li­suus on, et­tä jäl­kim­mäi­nen vaih­to­eh­to to­teu­tuu ja suo­ri­tus to­del­la­kin vie enem­män kuin n as­kel­ta. Kos­ka ali­oh­jel­ma täs­sä ta­pauk­ses­sa te­kee apt:n kut­su­mi­sen li­säk­si hy­vin vä­hän muu­ta, ai­noa paik­ka jos­sa voi ku­lua pal­jon as­ke­lia on apt:n suo­ri­tus. Sik­si apt:n suo­ri­tus vie täs­sä ta­pauk­ses­sa vää­jää­mät­tä mel­kein n as­kel­ta.

Täl­lai­nen ti­lan­ne saa­daan ai­kaan pa­lau­te­laa­ti­kon ylä­puo­lel­ta löy­ty­väl­lä ξ_n(σ):lla. Lu­ku­ar­vo n on pan­tu ala­in­dek­siin, kos­ka se ei ole osa syö­tet­tä vaan on kir­joi­tet­tu sel­lai­se­naan oh­jel­ma­koo­diin nu­me­ro­mer­keil­lä 0, 1, …, 9. Konk­re­ti­soi­dak­sem­me tä­tä tar­kas­te­lem­me en­sin ti­lan­net­ta, jos­sa n:n ar­vo on tu­hat, eli tar­kas­te­lem­me seu­raa­vaa ali­oh­jel­maa:

ξ₁₀₀₀(σ ∈ Σ*) ∈ ℕ
j := 0
if apt(σ, σ, 1000) then
   for i := 1 to 1000 do
      j := j + 1
return j

Kut­sun ξ₁₀₀₀(ξ₁₀₀₀) suo­ri­tus ete­nee ja ku­lut­taa suo­ri­tus­as­ke­lia seu­raa­vas­ti:

• j nol­la­taan. Tä­hän ku­luu yk­si as­kel.
• Aje­taan apt(ξ₁₀₀₀, ξ₁₀₀₀, 1000) eli tes­ta­taan, esit­tää­kö merk­ki­jo­no ξ₁₀₀₀ ali­oh­jel­maa, jol­la on yk­si­osai­nen syö­te jo­ka on merk­ki­jo­no, ja jon­ka suo­ri­tus kes­tää enin­tään tu­hat as­kel­ta sii­nä ta­pauk­ses­sa, et­tä syöt­tee­nä on merk­ki­jo­no ξ₁₀₀₀. Ali­oh­jel­man apt(ξ₁₀₀₀, ξ₁₀₀₀, 1000) suo­rit­ta­mi­seen ku­luu jo­kin mää­rä as­ke­lia, jo­ta mer­kit­sem­me kir­jai­mel­la z. Li­säk­si then- tai else-haa­ran va­lin­taan ku­luu yk­si as­kel.
• Jos tes­tin tu­los oli T, niin suo­ri­te­taan for-sil­muk­ka, jo­ka kier­tää tu­hat kier­ros­ta. Muut­tu­jan j ar­vo kas­vaa kier­ros kier­rok­sel­ta ja on lo­puk­si 1000. Lo­puk­si ali­oh­jel­ma pa­laut­taa tu­lok­se­naan lu­vun 1000. For-sil­mu­kan suo­rit­ta­mi­seen me­nee 4001 as­kel­ta: j + 1 las­ke­taan tu­hat ker­taa, sen tu­los si­joi­te­taan j:hin tu­hat ker­taa, i kas­va­te­taan tu­hat ker­taa, ja tes­ti on­ko i enin­tään 1000 suo­ri­te­taan 1001 ker­taa, jois­ta vii­mei­ses­sä i = 1001 ja for-sil­mu­kas­ta tul­laan ulos. Tu­lok­sen pa­laut­ta­mi­seen me­nee yk­si as­kel. Kuin­ka mon­ta as­kel­ta ali­oh­jel­man suo­rit­ta­mi­seen me­nee kai­ken kaik­kiaan? ok_text Oi­kein! f_nodes 3 hide_expr z+4004 =
  tai
• Jos tes­tin tu­los oli F, jä­te­tään for-sil­muk­ka suo­rit­ta­mat­ta ja pa­lau­te­taan tu­lok­se­na lu­ku 0. Tä­hän me­nee yk­si as­kel. Kuin­ka mon­ta as­kel­ta ali­oh­jel­man suo­rit­ta­mi­seen me­nee kai­ken kaik­kiaan? ok_text Oi­kein! f_nodes 3 hide_expr z+3 =
  tai

Saim­me siis tu­lok­sek­si, et­tä jos ξ₁₀₀₀(ξ₁₀₀₀):n suo­ri­tus kes­tää enin­tään 1000 as­kel­ta, niin ξ₁₀₀₀(ξ₁₀₀₀):n suo­ri­tus kes­tää näin mon­taz + 4004 as­kel­ta (then-haa­ra), ja jos ξ₁₀₀₀(ξ₁₀₀₀):n suo­ri­tus kes­tää yli 1000 as­kel­ta, niin ξ₁₀₀₀(ξ₁₀₀₀):n suo­ri­tus kes­tää näin mon­taz + 3 as­kel­ta (else-haa­ra). Toi­nen näis­tä vaih­to­eh­dois­ta on mah­do­ton. Kum­pi ja mik­si? vas­tausthen-haa­ras­sa suo­ri­tus kes­tää enin­tään 1000 ja täs­mäl­leen z + 4004 as­kel­ta. Kos­ka z on ali­oh­jel­man suo­ri­tus­as­kel­ten mää­rä ja sik­si po­si­tii­vi­nen, z + 4004 > 4004. Suo­ri­tus kes­tää siis enin­tään 1000 ja enem­män kuin 4004 as­kel­ta, mi­kä on mah­do­ton­ta.

Suo­ri­tus me­nee siis vält­tä­mät­tä xxxelse-haa­ran kaut­ta. Kat­so­mal­la edel­tä, kuin­ka mon­ta as­kel­ta suo­ri­tus kes­tää täs­sä haa­ras­sa ja mil­lä eh­dol­la tä­hän haa­raan men­nään, saam­me tä­mänz + 3 > 1000 epä­yh­tä­lön. Sen rat­kai­su on tä­mäz > 1000 − 3 = 997.

Käym­me nyt päät­te­lyn uu­del­leen lä­pi si­ten, et­tä lu­vun 1000 pai­kal­la on mi­kä ta­han­sa luon­nol­li­nen lu­ku n. Then-haa­ran kaut­ta kul­jet­taes­sa ξ_n(ξ_n):n suo­ri­tus­as­kel­ten mää­rä on ok_text Oi­kein! f_nodes 7 hide_expr 4n+4+z = ja else-haa­ran kaut­ta kul­jet­taes­sa end_of_answer arithmetic f_nodes 3 hide_expr 0n+3+z = .
tai

Jos then-haa­raan men­nään, pä­tee epä­yh­tä­lö ok_text Oi­kein! modulo 13 f_nodes 9 hide_expr 4n+z+4 ≤ n ⇔ ≤ n. Sen rat­kai­su on modulo 13 f_nodes 8 hide_expr z ≤ -3n-4 ⇔ z ≤. Täl­löin z on ne­ga­tii­vi­nen, mi­kä on mah­do­ton­ta, kos­ka z on ali­oh­jel­man suo­ri­tus­as­ke­lien mää­rä. Sik­si ali­oh­jel­ma ei me­ne then-haa­raan.
tai

Jos else-haa­raan men­nään, pä­tee epä­yh­tä­lö ok_text Oi­kein! modulo 13 f_nodes 5 hide_expr z+3 > n ⇔ >, jon­ka rat­kai­su on modulo 13 f_nodes 5 hide_expr z > n-3 ⇔ z >.
tai

Ku­ten edel­lä to­te­sim­me, tar­kat nu­mee­ri­set ar­vot riip­pu­vat oh­jel­moin­ti­kie­len va­lin­nas­ta. Oh­jel­moin­ti­kie­len va­lin­nas­ta riip­pu­ma­ton tu­los on, et­tä on ole­mas­sa jo­kin sel­lai­nen n:stä riip­pu­ma­ton po­si­tii­vi­nen va­kio b, et­tä z > n − b.

Mi­tä ξ_n(ξ_n):n suo­ri­tuk­ses­sa ta­pah­tuu, jos apt:ina on spapt? vas­tausj nol­la­taan ja käyn­nis­te­tään spapt(ξ_n, ξ_n, n). Se tut­kii on­ko ξ_n ajsoym, to­teaa et­tä se on, ja suo­rit­taa ξ_n(ξ_n):ää enin­tään n as­kel­ta tai kun­nes se py­säh­tyy. Tä­mä si­sem­pi ξ_n(ξ_n):n suo­ri­tus al­kaa sa­moin kuin ulom­pi­kin, eli nol­laa oman j:nsä ja käyn­nis­tää spapt(ξ_n, ξ_n, n):n, jo­ka tut­kii ξ_n:n ja al­kaa suo­rit­taa ξ_n(ξ_n):ää. Näin syn­tyy uu­sia ja uu­sia si­säk­käi­siä ξ_n(ξ_n):n suo­ri­tuk­sia, jois­ta jo­kai­nen ajaa omaa ko­pio­taan spapt(ξ_n, ξ_n, n):sta. Lo­pul­ta uloim­man spapt(ξ_n, ξ_n, n):n as­kel­las­ku­ri eli n saa­vut­taa nol­lan, jol­loin uloin spapt(ξ_n, ξ_n, n) lo­pet­taa ja pa­laut­taa F. Sen seu­rauk­se­na uloin ξ_n(ξ_n) pa­laut­taa 0. Uloim­man spapt(ξ_n, ξ_n, n):n lo­pet­taes­sa lop­pu­vat sa­man­tien myös kaik­ki muut spapt(ξ_n, ξ_n, n):t ja kaik­ki pait­si uloin ξ_n(ξ_n), kos­ka ne oli­vat vain si­mu­laa­tio, si­mu­laa­tion si­säl­tä­mä si­mu­laa­tio, si­mu­laa­tion si­säl­tä­män si­mu­laa­tion si­säl­tä­mä si­mu­laa­tio ja niin edel­leen uloim­man spapt(ξ_n, ξ_n, n):n suo­ri­tuk­ses­sa.

Tyh­jän syöt­teen py­säh­ty­mis­tes­te­riä ei ole

Ei ole vai­keaa kir­joit­taa ali­oh­jel­ma, jo­ta tois­tu­vas­ti kut­su­mal­la saa­daan kaik­ki merk­ki­jo­not ly­him­mäs­tä al­kaen. Sa­man­pi­tui­set merk­ki­jo­not se tuot­taa aak­kos­jär­jes­tyk­ses­sä. Al­la merk­ke­jä ovat ha­vain­nol­li­suu­den vuok­si vain nu­me­ro­mer­kit. Mer­kis­tä saa­daan seu­raa­va li­sää­mäl­lä sii­hen 1.

seuraava(σ ∈ Σ*) ∈ Σ*
i := 1
while i ≤ σ.pituus ∧ σ[i] = ’9’ do
   σ[i] := ’0’
   i := i + 1
if i ≤ σ.pituus then
   σ[i] := σ[i] + 1
else
   lisää σ:n loppuun '0'

Tyh­jän syöt­teen py­säh­ty­mis­tes­te­ri ot­taa syöt­teek­seen merk­ki­jo­non π ja pa­laut­taa T tai F sen mu­kaan, on­ko π:n si­säl­tö ali­oh­jel­ma, jon­ka tu­lok­sen tyyp­pi on merk­ki­jo­no ja jo­ka py­säh­tyy tyh­jäl­lä syöt­teel­lä. Jos tyh­jän syöt­teen py­säh­ty­mis­tes­te­ri oli­si ole­mas­sa, niin jo­kai­sel­la luon­nol­li­sel­la lu­vul­la k voi­tai­siin to­teut­taa seu­raa­va ali­oh­jel­ma κ_k. Ala­in­dek­si k on while-sil­mu­kan eh­dos­sa esiin­ty­vän lu­vun nol­lien mää­rä.

κ₄ ∈ Σ*
π := ””;  τ := ”Merkkijonoja: ”
while π.pituus ≤ 10000 do
   if π pysähtyy tyhjällä syötteellä then
      suorita π tyhjällä syötteellä ja lisää sen tulos τ:n perään
   π := seuraava(π)
return τ

Py­säh­tyy­kö κ_k:n suo­ri­tus? vas­tausKyl­lä. while-sil­mu­kan kier­ros­ten mää­rää ra­joit­taa enin­tään 10^k merk­kiä pit­kien merk­ki­jo­no­jen mää­rä, jo­ka on ää­rel­li­nen. if-lau­seen tes­ti ole­tet­tiin mah­dol­li­sek­si. π suo­ri­te­taan vain jos sen suo­ri­tus tu­lee py­säh­ty­mään. Kaik­ki muu on sel­väs­ti py­säh­ty­vää.

Mer­kit­sem­me κ₀:n pi­tuut­ta m:llä. κ_k:n pi­tuus on m + k. Ol­koon π mi­kä ta­han­sa ali­oh­jel­ma, jon­ka pi­tuus on enin­tään 10^k, jon­ka tu­lok­sen tyyp­pi on merk­ki­jo­no ja jo­ka py­säh­tyy tyh­jäl­lä syöt­teel­lä. Täs­tä syys­täκ_k suo­rit­taa π:n (ja kaik­ki muut­kin sa­mat eh­dot täyt­tä­vät ali­oh­jel­mat) ja ot­taa π:n tu­lok­sen osak­si vas­taus­taan. κ_k:n vas­tauk­ses­sa on li­säk­si muu­ta­kin, ai­na­kin sa­na ”Merkkijonoja: ”. κ_k:n pa­laut­ta­man merk­ki­jo­non pi­tuus on enem­män kuin π:n pa­laut­ta­man merk­ki­jo­non pi­tuus.

Sik­si κ_k ei voi ol­la π. Näin ol­len κ_k:n pi­tuus on enem­män kuin 10^k, jo­ten saam­me m + k > 10^k. Tä­mä on mah­do­ton­ta, jos va­li­taan tar­peek­si suu­ri k. Esi­mer­kik­si va­lit­se­mal­la k = m saa­daan 2m > 10^m, jo­ka ei ole tot­ta mil­lään luon­nol­li­sel­la lu­vul­la m.

Mik­si meil­lä oli lu­pa va­li­ta k, kun yleen­sä to­dis­tuk­sis­sa väi­te pi­tää to­dis­taa jo­kai­sel­le ar­vol­le? Täs­tä syys­täEdel­lä pe­rus­tel­tiin, et­tä jos tyh­jän syöt­teen py­säh­ty­mis­tes­te­ri on ole­mas­sa, niin κ_k on ole­mas­sa jo­kai­sel­la k ∈ ℕ. Jos yh­del­lä­kin k syn­tyy ris­ti­rii­ta, ei κ_k ole ole­mas­sa jo­kai­sel­la k ∈ ℕ, jo­ten tyh­jän syöt­teen py­säh­ty­mis­tes­te­riä­kään ei ole.

Lo­puk­si

Edel­li­ses­sä lu­vus­sa otim­me as­ke­leen koh­ti Kol­mo­go­rov-komp­lek­si­suut­ta. Sii­nä merk­ki­jo­non si­säl­tä­män in­for­maa­tion mää­räk­si mää­ri­tel­lään ly­hyim­män sel­lai­sen ali­oh­jel­man pi­tuus, jo­ka tyh­jäl­lä syöt­teel­lä tu­los­taa ky­sees­sä ole­van merk­ki­jo­non ja py­säh­tyy. Kol­mo­go­rov-komp­lek­si­suus vas­taa hy­vin in­tui­tio­tam­me sii­tä, et­tä merk­ki­jo­no ”Oikein!” si­säl­tää enem­män in­for­maa­tio­ta kuin yh­tä pit­kä merk­ki­jo­no ”ooooooo”. Kol­mo­go­rov-komp­lek­si­suu­den käyt­tö­kel­poi­suut­ta vä­hen­tää to­del­la ra­ju rat­kea­mat­to­muus­tu­los, jo­hon eh­kä vie­lä jos­kus tu­tus­tum­me.