*Ustavljivost algoritma

Algoritem je ustavljiv, če se pri vseh veljavnih vhodih prej ali slej ustavi. Ni pomembno, po koliko korakih oziroma po kolikšnem času se ustavi. Pomembno je le, da se ustavi. Ustavljivost je vprašljiva le tedaj, ko algoritem vsebuje zanke ali rekurzivne klice funkcij. V nasprotnem primeru se namreč algoritem vedno ustavi.

Ustavljivosti v splošnem ni mogoče dokazati. Za nekatere algoritme namreč ne znamo (ali celo ne moremo) ugotoviti, ali se ustavijo pri vseh veljavnih vhodih. Enega od takšnih algoritmov bomo spoznali pozneje, sedaj pa si oglejmo pravilo, ki nam lahko pomaga vsaj pri nekaterih enostavnih zankah. Enojno zanko lahko opredelimo kot ustavljivo, če nam uspe na podlagi spremenljivk, ki nastopajo v programu, zapisati izraz, čigar vrednost je na začetku vsakega obhoda zanke neko pozitivno celo število, obenem pa se v vsakem obhodu zanke zmanjša vsaj za 1. Ker takšen izraz ne more biti manj kot 1 (razen morda v zadnjem obhodu zanke), se zanka gotovo prej ali slej ustavi. Na primer če je začetna vrednost izraza enaka 10, se bo zanka izvedla kvečjemu 10-krat.

Dokažimo ustavljivost tega algoritma:

Ali lahko poiščemo izraz, čigar vrednost je na začetku vsakega obhoda zanke pozitivno celo število, obenem pa se v vsakem obhodu zmanjša vsaj za 1?

Poglejmo. Izraz i+1 je v vseh obhodih zanke pozitiven, vendar pa narašča, namesto da bi padal (na začetku prvega obhoda ima vrednost 1, na začetku drugega 2 itd.). Izraz n nam nič bolj ne koristi, saj se ne spreminja. Drugače pa je z izrazom n-i, ki predstavlja število še ne prištetih števil. Ta izraz je v vseh obhodih zanke pozitiven (na začetku prvega obhoda ima vrednost n, na začetku drugega n-1 itd.), obenem pa se vsakokrat zmanjša za 1. Zato lahko trdimo, da se zanka (in s tem celotna funkcija oz. celoten algoritem) ustavi. Oglejmo si še en algoritem:

Ali pri vseh pozitivnih celih številih n prej ali slej pridemo do enice in se ustavimo? Odgovor se glasi: ne vemo! Doslej še nikomur ni uspelo dokazati oziroma ovreči te t.i. Collatzove domneve. (Domnevo bi ovrgli, če bi našli število n, pri katerem se algoritem ne ustavi.) Že pri nekaterih razmeroma majhnih številih je pot do enice kar dolga (npr. 15 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1), kljub temu pa je računalnikarjem in matematikom s sistematičnim izvajanjem programa uspelo pokazati, da do enice prej ali slej vodijo vsa števila do najmanj 10¹⁸. Žal pa to še ni dokaz, saj je celih števil neskončno. Zaenkrat problem še vedno ostaja odprt; morda ga boš rešil(-a) prav ti!