Citat:
FuzzyCreation: Programski jezik jeste formalni jezik, te je model programskog jezika (skup leskickih, sintaksnih i semantickih pravila) jedna formalna teorija.
- Skup svih reči nad nekim alfabetom je skup svih konačnih nizova čiji su članovi slova tog alfabeta, uključujući i prazan niz kao reč dužine nula koja se ne sastoji ni od jednog slova tog alfabeta.
- Formalni jezik čine alfabet i skup reču tog jezika, koji je izvestan podskup skupa svih reči nad tim alfabetom.
- Formalnu teoriju čine alfabet, skup formula (koji je podskup skupa svih reči nad tim alfabetom i zajedno sa alfabetom čini jezik te formalne teorije), skup aksioma koji je podskup skupa formula i skup pravila izvođenja koja su relacije sa bar dva argumenta.
- Formalnu gramatiku čine dva disjunktna alfabeta, skup završnih i skup nezavršnih slova, početno slovo, koji je nezavršno slovo i skup pravila izvođenja, koja su relacije sa dva argumenta nad skupom svih reči sa slovima iz unije oba alfabeta.
- Formalnoj gramatici pridružujemo jezik sa istim alfabetom, čiji je skup reči skup svih reči nad sskupom završnih slova, koja se mogu dobiti konačnom primenom pravila izvođenja polazeći od početnog slova. Međutim, jezik se ne mora zadavati preko gramatike i različite gramatike mogu dazi isti jezik, tako da treba voditi računa o pravljenju razlike između tih pojmova.
- Formalna gramatika je, u odnosu na formalni jezik, bliži pojam formalnoj teoriji, jer osim alfabeta (koji u slučaju formalne gramatike obuhvata dve vrste slova - završna i nezavršna) ima i pravila izvođenja, kao i početni simbol kao aksiomu. Međutim, da bismo dobili formalnu teoriju, treba na neki način zadati i skup formula.
Skup formula mora biti podskup skupa svih reči nad odgovarajućim alfabetom, koji obuhvata sve reči odgovarajućeg formalne gramatike (jer će one biti teoreme te formalne teorije, kao reči izvodive u konačnom broju koraka polazeći od početnog simbola konačnom primenom pravila izvođenja). Obratiti pažnju da skup svih reči formalne gramatike nije isto što i skup svih reči nad njenim alfabetom.
Zbog toga, način pridruživanja skupa formula nije jednoznačno određen, pa ne postoji podrazumevani (dogovoreni) način pridruživanbja formalnih teorija formalnim gramatikama. No. možemo se mi dogovoriti, za potrebe ove rasprave oko načina na koji ćemo birati skup formula.
Ako skup formula definišemo kao skup svih reči date formalne gramatike, onda če se skup formula biti isto što i skup teorema, pa će ta formalna teorija svakako biti kompletna i protivrečna, bez obzira od kakve smo gramatike pošli. Ako li pak skup formula definišemo kao skup svih reči nad odgovarajućim alfabetom, onda će ta formalna teorija biti protivrečna ako isamo ako su sve reči nad tim alfabetom izvodive u toj formalnoj gramatici. Napominjem da ceo ovaj pasus nema nikave veze sa Gedelovim teoremama nepotpunosti.
Dakle, lako je formalnoj gramatici pridružiti formalnu teoriju čiji će skup teorema biti skup svih reči te gramatike, ali kompletnost te teorije bitno zavisi od toga kako joj definišemo skup formula.
Citat:
FuzzyCreation: Ako za jedan semanticki koncept imas vise sintaksnih konstrukcija gubi se minimalnost,
na primer za petlju imas FOR, WHILE i REPEAT sintaksne konstrukcije.
Prvo, takav pojam minimalnosti zavisi od izbora semantike datog programskog jezika. Drugo, koji je programski jezik u tom smislu minimalan? Možeš ubacivati komentare i preoznačavati promenljive koliko god hoćeš. U programskim jezicima u kojima nema provere granica indeksa upotrebu n promenljivih istog tipa možeš zameniti upotrebom niza od tri elementa, jer se adrese članova sa konstantnim indeksima izračunavaju u fazi prevođenja, pa dobijaš isti izbršni fajl. Nije teško zamisliti semantiku programskog jezika BASIC u jojoj će sledeća dva BASIC programa imati istu semantiku:
Code:
10 LET I=1
20 IF I>100 THEN STOP
30 GOSUB 100
40 LET I=I+1
50 GO TO 20
100 PRINT I
110 RETURN
10 LET I=1
20 IF I>100 THEN STOP
30 GOSUB 100
40 LET I=I+1
50 IF I>100 THEN STOP
60 GOSUB 100
70 LET I=I+1
80 GO TO 20
100 PRINT I
110 RETURN
Nije teško zaključiti da ni Tjuringova mašina nije u tom smislu minimalna.
Citat:
FuzzyCreation: Neprotivurecnost programskog jezika kao formalnog jezika jeste apriorna.
Pod njom se podrazumeva to da svaki program u nekom programskom jeziku uvek na isti input daje isti output.
Da nije tako izgubio bi se toliko nam drag determinizam algoritma, tj. izgubili
bi mogucnost funkcionalnog intepretiranja, kao i kompajliranja (ovo je otprilike
objasnjenje na ono ???)
A šta ćemo sa programskim jezicima kao što su Java i (sve popularniji) C#, koji zbog nepredvidivosti trenutka uključivanja skupljača đubreta gube determinizam?
Citat:
FuzzyCreation: Komplentnost programskog jezika jeste kompletnost u smislu izracunljivosti, jezik mora biti takav da pokrije skup svih izracunljivih funkcija.
I kakve onda ima veze taj pojam kompletnosti sa Gedelovim teoremama nepotpunosti? Naprotiv, po definicijama koje si ovde naveo, svi programski jezici su kompletni, a najveći broj njih je deterministički (ili "neprotivrečan", kako ti kažeš).
Citat:
FuzzyCreation: Formalna teorija je neprotivurecna ako se u njoj ne moze izvesti iskaz A i njegova negacija. Ako bar jedna formula neke formalne teorije nije njena teorema to ne znaci da u skupu teorema nema jednu teoremu i njenu negaciju koja je takodje teorema.
A šta ćemo sa formalnim teorijama u kojima nemamo negaciju? Recimo, alfabet se sastoji od slova a i b. Ako formalna teorija opisuje ili obuhvata nekakvu logiku (a ne mora opisivati, niti obuhvatati nikakvu logiku), koja obuhvata negaciju (a logika ne mora obavezno da obuhvata negaciju), onda u najvećem broju slučajeva (što je slučaj npr. kod klasične logike), a u zavisnosti od toga koja je logika u pitanju, sve formule su teoreme ako i samo ako postoji teorema čija je negacija takođe teorema.
Citat:
FuzzyCreation: Ima koliko god hoces neprotivurecnih i kompletnih formalnih teorija, ali krajnje
beskorisnih sa stanovista izracunljivosti. U mojoj recenici kada sam rekao da se
ne moze zahtevati potpunost formalne teorije ako zahtevamo neprotivurecnost, ono
formalne teorije se odnosilo na programski jezik. Formalno gledano recenica nije
ispravna kada se izvuce iz konteksta. Jasno je da postoje neprotivurecne i
kompletne formalne teorije, ali ne nivou ranga jednog ozbiljnijeg (funkcionalnijeg)
programskog jezika.
Onako kako si definisao pojmove "neprotivrečnosti" (?) i kompletnosti programskij jezika, oni nemaju nikakve veze sa pojmovima neprotivrečnosti i kompletnosti formalnih teorija, pa ni sa Gedelovim teoremama nepotpunosti. Tjuringova mašina je deterministički i kompletan sistem izračunljivosti.
Citat:
FuzzyCreation: Svrha minimalizma nije da postoje neki koncepti koji prosiruju isti taj minimalizam i cime se gubi smisao istog, nego da se svesno ogranice neke stvari zbog razno raznih pojava i fenomena koje bi bile moguce kada iste ne bi bile ogranicene. Stoga sta ce mi minimalni programski jezik koji mi nudi predprocesorske mogucnosti prosirenja. Gubi se smisao i odjednom uvidjas da ti je vise koda u predprocesoru nego u samom
jeziku.
A čemu minimalizam, kada nije ostvariv?
[Ovu poruku je menjao Nedeljko dana 23.01.2007. u 17:34 GMT+1]
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.