Što se tiče Knutovog citata, to ipak nije definicija algoritma, već pojašnjenje čitaocu, dovoljno dobro za praćenje te knjige. U suprotnom ispade sve rešivo u jednom koraku - Neka je uz Knutovu simboliku g:I->O funkcija definisana na sledeći način:
1. Ako niz x=x0,x1,...,xk=y predstavlja izračunavanje po Knutu, onda je g(x)=y.
2. U suprotnom je g(x)=x.
Definiši izračunavanje sa istim skupovima Q,I,O, samo sa funkcijom prelaza g umesto f i dobićeš rešavanje potpuno istog problema u jednom koraku. Dakle, tako ispada da mu nizovi i ne trebaju.
Štaviše, to je "algoritamsko rešenje" za ma koji problem, gde je g(x) željeni izlaz za ulaz x, pa svi problemi ispadoše algoritamski rešivi u jednom koraku.
Neka je Q skup svih ASCII fajlova, I skup svih sintaksno ispravnih programa na nekom programskom jeziku, koji ne prihvataju nikakave ulaze, već su svi podaci upisani u pogram, O skup fajlova koji se sastoje od samo jednog znaka 0 ili 1, onda neka je f(x)=1 ako se program x zaustavlja u konačnom broju koraka, a inače f(x)=0. Funkcija prelaza je taman takva da problem zaustavljanja rešavaš u jednom koraku. Znači, dobio si "algoritam" za rešavanje problema zaustavljanja. Da li bi mogao da ga isprogramiraš?
Knut je inače iz pedagoških razloga umeo da daje u početku približne definicije, pa tek kasnije korektne, ako je potrebno. Inače, bez ikakvih ograničenja za funkciju prelaza ova definicija nema previše smisla
Citat:
retard378: i da dodam ja nisam pokusao da dam definiciju algoritma vec sam samo odgovorio na temu tako sto sam naveo definiciju iz ipak vodece knjige iz ove oblasti,ako mislis da se druga imena ne bi slozila sa njim mogo bi da das referene za ta neslaganja
u svakom slucaju svako moze da se "ne slozi" sa definicijom i da pod definisanim pojmom smatra nesto sire ili uze od toga sto definicija obuhvata ali je to toliko besmisleno i dovelo bi samo do radjanja milijardu teorija o jednoj stvari
Šta znam koja je vodeća. Možda je ta vodeća programerska iz te oblasti. Ima drugih knjiga sasvim drugačije koncepcije iz te oblasti, koje koriste studenti poslediplomskih studija, kao što su na primer
1. "Recursion theory", Joseph Schoenfeld,
2. "Computability", Nigel Cutland
i da ne navodim druge. Mogao bi ti da navedeš bar jednu teoriju gde je strogo zasnovan pojam zaustavljivih procedura nezavisno od opšteg pojma mehaničkih procedura (da ne bude definicija mehaničke procedutre, pa onda specijalan slučaj kada je ona zaustavljiva). Ja znam više sistema izračunljivosti (sistem rekurzivnih funkcija, URM mašine, Tjuringove mašine itd.), gde je obavezno opisan pojam mehaničkih procedura uključujući i nezaustavljive.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.