Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
ustawićwszystkieprogramywciąg,ton-typrogramdajenan-tym
miejsculiczbyΩcyfrę0,jeślisięniezatrzymaicyfrę1,jeślisię
zatrzyma.GdybyśmypotrafilinapisaćliczbęChaitinaΩ,toproblem
stopubyłbyrozwiązalny,awiadomo,żejestonnierozwiązalny.
AzatemliczbaChaitinajestnieprzywiedlna.
OczywiściemożnaobliczyćtrochęmiejscliczbyChaitina,
powiedzmyN,aleprogramtakiniemożebyćznaczącokrótszyniżN
izawszepozostanienieskończeniewielemiejsc,którychtakiprogram
niepoliczy.Jeślichcemyznaćtychmiejscwięcej,musimydodać
więcejinformacji(aksjomatów).Sytuacjaprzypominatwierdzenie
Gödlaoniezupełności;Chaitinnazywato„extremelystrong
incompletenessresult”[43].
Rozważaniatemogąsię
wydawaćodległeodpraktyki
matematycznej,jednakżeChaitinwiążeswojąliczbęΩzrównaniami
diofantycznymi.Problem10Hilbertabyłtaki:czyistniejemetoda
rozstrzygania
istnienia
rozwiązania
dla
danego
równania
diofantycznego?W1970r.Matijasewiczpokazał,żeproblemtenjest
równoważnyproblemowistopu.Chaitinpokazuje,żemającdaną
maszynęTuringamożemyzbudowaćrównaniediofantyczne,które
marozwiązaniewtedyitylkowtedy,gdymaszynasięzatrzyma.Ina
odwrót,mającdanerównaniediofantycznemożemyzbudować
maszynęTuringa,którasięzatrzymawtedyitylkowtedy,gdy
równaniemarozwiązanie[44].Ibudujeparametrycznysystemrównań,
którysięwiążezliczbąChaitinawnastępującysposób:jeślina
miejscuNliczbyΩjest0,torównaniewyznaczoneprzezliczbęNma
skończeniewielerozwiązań,ajeśli1,tonieskończeniewiele
rozwiązań[45].
I
wyciąga
stąd
wniosek,
że
problemy
nierozstrzygalnościiniezupełnościstałysiębardzobliskiecodziennej
matematyki.
11.Innespojrzenienamatematykę
Sukcesy
metody
aksjomatyczno-dedukcyjnej
sprawiły,
że
towarzyszącajejrefleksjakrytycznaniehamujejejstosowaniainie
wpływaistotnienarozwójmatematyki.Refleksjatadotyczykilku
spraw: