Nepotpunost (još jednom, najjednostavnije)

Svaki računalni program možemo zapisati kao konačni niz nula i jedinica. Takve programe zvat ćemo 0,1-programima

Niz nula i jedinica duljine n zvat ćemo reducibilnim ako postoji 0,1-program koji generira taj 0,1-niz i čija je duljina manja od n. Ako takav program ne postoji niz ćemo zvati ireducibilnim.

0,1-nizova duljine n ima 2n.

0,1-programa duljine manje od n ima  najviše 1 + 2 + 22 + … + 2n = 2n _ 1.

To znači da bar jedan 0,1-niz duljine n nije reducibilan.

Dakle, postoji beskonačno mnogo ireducibilnih konačnih nizova. (Bar jedan za svaku duljinu n.)

Možemo li formalno korektno i potpuno dokazivati ireducibilnost konačnih 0,1-nizova?

Svakom formalnom sustavu dokazivanja može se pridružiti program koji generira njegove dokaze (on u biti i jest takav jedan program).

Dakle i formalnom sustavu koji dokazuje ireducibilnost konačnih 0,1-nizova.

Pridružimo tom formalnom sustavu 0,1-program koji generira konačne 0,1-nizove, uz eventualne dokaze njihove ireducibilnosti, i njegovu duljinu označimo s N.

Ako je sustav potpun (tj. ako dokazuje sve istine) program bi trebao generirati beskonačno mnogo dokaza ireducibilnosti, što znači da bi uz dokaz njegove ireducibilnosti generirao i neki 0,1-niz koji je duži od N (jer je kračih od N samo konačno mnogo).

Ako je korektan (tj. ako dokazuje samo istine) ne bi smio uz dokaz njegove ireducibilnosti generirati niti jedan 0,1-niz duži od N (jer bi taj niz tada bio reducibilan).

Zato program, a stoga i početni formalni sustav, koji dokazuje ireducibilnost konačnih 0,1-nizova ne može biti korektan i potpun.

Ili, još preciznije, ako je formalni sustav dokazivanja ireducibilnosti 0,1-nizova korektan onda on može dokazati ireducibilnost tek konačnog broja ireducibilnih nizova, iako ih ima beskonačno mnogo.

Oglasi

O autoru zsikic

https://www.fsb.unizg.hr/matematika/sikic/
Ovaj unos je objavljen u filozofija, logika, matematika i označen sa , . Bookmarkirajte stalnu vezu.

2 odgovora na Nepotpunost (još jednom, najjednostavnije)

  1. Jadranka Delac-Klepac napisao:

    Hvala, ovo je izvrsno! Jadranka >

Komentiraj

Please log in using one of these methods to post your comment:

WordPress.com Logo

Ovaj komentar pišete koristeći vaš WordPress.com račun. Odjava / Izmijeni )

Twitter picture

Ovaj komentar pišete koristeći vaš Twitter račun. Odjava / Izmijeni )

Facebook slika

Ovaj komentar pišete koristeći vaš Facebook račun. Odjava / Izmijeni )

Google+ photo

Ovaj komentar pišete koristeći vaš Google+ račun. Odjava / Izmijeni )

Spajanje na %s