[MD-sorular] Peano Aksiyomlariyla dogal sayilar arasindaki ayrim (Das Entscheidungsproblem)

tibet efendi tibetefendi at yahoo.com
31 Ara 2009 Per 16:25:10 EET


Gecen sene bilgisayar dersinde görmüstüm, durma problemi su:

Bir dogal sayiyi alip, Gödel kodu o dogal sayi olan bir Turing Makinasi'nin (eger varsa) her girdide durup durmadigina karar veren bir Turing makinasi var midir?
Cevap: yoktur.

Her ne kadar cok benzer görünseler de benim yazdigim kanit makinasi meselesiyle bu problem birbirlerinden farkli.

Turing makinasini kanit makinasi olarak düsünürsek, Turing'in durma problemine verdigi cevap su anlama geliyor:
Kanit makinasina bir önerme verdigimizde makina onu kanitlamaya calisiyor. Ve önerme dogruysa mutlaka kanitliyor olsun. (önce tartistigimiz konuda bu, böyle degildi, makinanin kanitlayamadigi dogru önermeler vardi). Ama önerme dogru degilse makina sonsuza kadar islem yapiyor olsun.
Turing diyor ki: Bir kanit makinasina bakip hangi formülde durduguna karar verecek baska bir makina insa edilemez.

Bu sorun bizimkinden farkli. Ikisinin neden ayni sey olmadigini bir de söyle izah edeyim:

Durma Probleminde dogal sayilardaki carpmadan toplamadan hic bahsetmeseniz de olur. Her seyi {0,1,#} alfabesiyle, carpma ve toplama islemleri olmadan yapabilirsiniz. Turing'in o iddiasini sadece bunlarla ortaya koyup kanitlayabilirsiniz.

Ama bizim tartistigimiz konuda Gödel'in eksiklik teoremi dogal sayilardaki carpma ve toplama islemlerine siki sikiya bagli.
Öyle bir farklilik var.

Yalniz tabi yine de birbiriyle alakali konular.

tibet



--- On Thu, 12/31/09, Kadir GÜLEÇ <kadir.gulec at spk.gov.tr> wrote:

From: Kadir GÜLEÇ <kadir.gulec at spk.gov.tr>
Subject: RE: [MD-sorular] Peano Aksiyomlariyla dogal sayilar arasindaki ayrim (Das Entscheidungsproblem)
To: "Tarik Ozkanli" <tarik.ozkanli at sampas.com.tr>, "tibet efendi" <tibetefendi at yahoo.com>, "Ali Nesin" <anesin at nesinvakfi.org>, "Matematik Dunyasi" <md-sorular at matematikdunyasi.org>
Date: Thursday, December 31, 2009, 1:37 AM




 
 






Problemin çözülemez olduğunu, lamda cebri
kavramını icat eden Alonzo Church gösteriyor, 1937 yılı sanırım. 

1938 yılında da Turing Makinaları ve
Evrensel Turing Makinası kavramlarını yaratan Alan Turing kanıtlıyor.  

Church-Turing teoremi deniyor.
(Church Turing savından farklı) 

Charles Petzold’un yazdığı
bir kitap var. 

Turing’in makalesini çok
güzel anlatmış. 

   

Kadir Güleç 

   

   

Merhaba, 

   

Bu kanit makinasindan istedigimiz su: 

"Buna bir aksiyom sistemi verecegiz. Bir de önerme verecegiz (carpma ve
toplamayi icerebilecek bu önerme) Bu makina bize o önermenin dogal sayilarda
dogru olup olmadigini söyleyecek. Sonlu bir zaman sonra söyleyecek. (cünkü o
makina dogal sayilarda dogru olan her önermeyi sayabiliyor olacak, sonsuza
kadar süren bir sayma islemi bu. Ama her dogru önerme eninde sonunda bu
makinanin agzindan dökülecek, biz öyle istiyoruz).

Makina bunu yapamiyorsa o zaman makinadan beklentimiz o önermenin degilinin
dogrulugunu söylemesi.

Yani phi önermesi verildiginde kanit makinasi bize ya phi'yi kanitlayacak ya da
phi degil'i"



Gödel diyor ki: Böyle bir makina olamaz.



Sanki yukarıdaki açıklama “Halting teoremi “ denilen
ve Alan Turing in ifade ettiği bir durumla daha çok örtüşüyor. 

Tabi Turing bu ifadeyi Gödel den sonra yazmış. 

“Hesaplanabilir sayılar üzerine” diye harika bir
makalesi var 1936 sanırım. 

   

Buradan ispat ile program (turing makinası) arasındaki
paralelliğe ve “type teorisi” ne geliyoruz. 

   

   



From: md-sorular-bounces at matematikdunyasi.org
[mailto:md-sorular-bounces at matematikdunyasi.org] On Behalf Of tibet
efendi

Sent: Thursday, December 31, 2009 4:48 AM

To: Ali Nesin; Matematik Dunyasi

Subject: Re: [MD-sorular] Peano Aksiyomlariyla dogal sayilar arasindaki
ayrim 



   


 
  
  
  Su son cevap cok aciklayici oldu, tesekkür ederim.

  

  Peki ikinci dereceden dediginiz (altkümeler hakkinda söz söyleyen) cümleyi
  neden aksiyom olarak kullanamiyoruz? Birinci dereceden mantik buna izin
  vermedigi icin mi?

  Peki o zaman bu tür ikinci dereceden cümlelerin kurulabildigi ikinci
  dereceden bir mantik vardir. Onunla yapmaya calisalim. O zaman da
  kanitlanabilir önermeler recursively enumerable olmaktan mi cikiyor?

  

  Eger öyleyse bütün bunlardan söyle bir sonuc cikariyorum:

  

  Bütün mesele bir kanit makinasi yapmak meselesi. Bu kanit makinasi
  lafini daha önce bir yerlerde görmüstüm, ne oldugunu simdi anladim galiba.

  

  Bu kanit makinasindan istedigimiz su: 

  "Buna bir aksiyom sistemi verecegiz. Bir de önerme verecegiz (carpma ve
  toplamayi icerebilecek bu önerme) Bu makina bize o önermenin dogal sayilarda
  dogru olup olmadigini söyleyecek. Sonlu bir zaman sonra söyleyecek. (cünkü o
  makina dogal sayilarda dogru olan her önermeyi sayabiliyor olacak, sonsuza
  kadar süren bir sayma islemi bu. Ama her dogru önerme eninde sonunda bu
  makinanin agzindan dökülecek, biz öyle istiyoruz).

  Makina bunu yapamiyorsa o zaman makinadan beklentimiz o önermenin degilinin
  dogrulugunu söylemesi.

  Yani phi önermesi verildiginde kanit makinasi bize ya phi'yi kanitlayacak ya
  da phi degil'i"

  

  Gödel diyor ki: Böyle bir makina olamaz.

  

  

  

  

  --- On Wed, 12/30/09, Ali Nesin <anesin at nesinvakfi.org>
  wrote: 
  

  From: Ali Nesin <anesin at nesinvakfi.org>

  Subject: Peano Aksiyomlariyla dogal sayilar arasindaki ayrim

  To: "tibet efendi" <tibetefendi at yahoo.com>

  Cc: "Matematik Dunyasi" <md-sorular at matematikdunyasi.org>

  Date: Wednesday, December 30, 2009, 4:49 PM 
  
  

  Bunu MD'de yazmadim. neden yazmadim bilmiyorum. Dalgaya dustum herhalde. Oysa
  cok ince, derin ve hos bir ayrinti.

  

  Dogal sayilar soyle bir yapidir:

  

  (N, S, 0) diye bir ucludur her seyden once.

  Burada:

  N bir kumedir.

  S : N ---> N bir fonksiyondur.

  0, N'nin bir elemanidir.

  Ayrica,

  S birebirdir.

  Ve S(N) = N \ {0} olur.

  Bunlar kolaydi. Simdi sonuncusu: Eger A, N'nin bir altkumesiyse ve A, 0'i
  iceriyorsa ve A'daki her a elemani icin S(a) da A'daysa, o zaman A = N olur.

  Kumeler kuraminda bu ozellikleri saglayan up to isomorphism bir ve bir tane
  (N, S, 0) yapisi vardir. Bir onceki yazimda betimledim bu yapiyi. Bunu
  kanitlamak da pek zor degildir.

  

  Peano Aksiyomlari'na gelelim, daha dogrusu Peano Aksiyomlarinin modellerine.

  Bu modeller de (N, S, 0) diye bir ucludur her seyden once.

  Burada:

  N bir kumedir.

  S : N ---> N bir fonksiyondur.

  0, N'nin bir elemanidir.

  Ayrica,

  S birebirdir.

  Ve S(N) = N \ {0} olur.

  Bunlar kolaydi. Simdi sonuncusu: Eger f(n), S ve 0 ile yazilan bir
  bilinmeyenli bir formulse ve f(0) dogruysa ve N'nin her n elemani icin f(n)
  dogru oldugunda f(S(n)) de dogru oluyorsa, o zaman f(n) formulu N'nin her
  elemani icin dogrudur.

  Bu sonuncusunu soyle ifade edeyim ki yukardakiyle ayrim daha iyi anlasilsin.
  Bir f(n) formulu icin A = {n in N : f(n) dogru} biciminde yazilan her kume
  yukardaki ozelligi saglar.

  

  Dikkat edersen ikincisi daha zayif. Birincisi tumevarimi her altkume icin
  verirken, ikincisi sadece bir formulle ifade edilebilen kumeler icin veriyor.

  

  Peano aksiyomlari "birinci dereceden" aksiyomlardir, yani sadece
  elemanlardan soz eder.

  Oysa ilk verdigim tanimda altkumelerden soz ediyordu.

  Peano aksiyomlari gibi birinci dereceden tumcelerden olusan teorilerin her
  kardinalitede (dolayisiyla izomorfic olmayan) modelleri vardir. Ama cok daha
  guclu bir sey soyleyecegim simdi: Peano aritmetiginin bircok modeli vardir.
  Bazi onermeler bu modellerin birinde dogrudur, bir digerinde yanlistir.
  Dogrusuyla bu tur onermeler Peano aritmetigiyle kanitlanamazlar. Bu da iste
  Godel!

  

  Ali

  N'nin bir altkumesiyse ve A, 0'i iceriyorsa ve A'daki her a elemani icin S(a)
  da A'daysa, o zaman A = N olur.

  Kumeler kuraminda bu ozellikleri saglayan up to isomorphism bir ve bir tane
  (N, S, 0) yapisi vardir. Bir onceki yazimda betimledim bu yapiyi. Bunu
  kanitlamak da pek zor degildir.

  

  

  

  

  tibet efendi wrote:

  > Tamam anladim biraz. Ama o zaman da su takiliyor kafama, belki cok basit
  ama cevabini bilmiyorum, sormam gerek:

  > (N, +, x, <, 0, 1) yapisinin ne oldugunu biz nereden biliyoruz?

  > Yani dogal sayilarin tanimini nasil yapiyoruz?

  > 

  > Dedik ki:

  > Dogal sayilar yapisinda dogru olan ama Peano Aksiyomlarindan (toplama
  carpma dahil) hareketle kanitlanamayan önermeler vardir.

  > Ama "dogal sayilar yapisinda dogru" oldugunu iddia ettigimiz o
  önerme, neye göre dogru, kime göre dogru? Dogrulugun tanimi ne? Dogal sayilar
  yapisinda dogru olmak ne demek?

  > 

  > Biz dogal sayilari zaten Peano Aksiyomlariyla tanimlamiyor muyuz?

  > O zaman dogal sayilar yapisi, Peano Aksiyomlarinin tanimlamaya gücünün
  yettiginin ötesinde bir sey midir?

  > Öyleyse nasil bir seydir?

  > Ne oldugunu biz de bilmiyorsak herhangi bir önermenin o yapida illa ya
  dogru ya da yanlis oldugunu (ikisi birden olamadigini) nereden biliyoruz?

  > 

  > Ayni sey Reel sayilar icin de gecerli. Onu da aksiyomlarla tanimladik
  sonucta.

  > 

  > Bana yaptigimiz sey su gibi geliyor:

  > "Aksiyomlarla tanimladigimiz yapidan o aksiyomlarin
  tanimlayabildiginin ötesinde bir sey olmasini bekliyor sonra öyle olmadigini
  görünce hayal kirikligina ugruyoruz"

  > 

  > Kafam o kadar karisti ki gögsüm sikisti.

  > Sanki bilmem gereken cok basit bir seyi bilmiyorum da o yüzden kafan
  karisiyor.

  > 

  > Neyi atliyorum? ya da nerede hata yapiyorum?

  > 

  > tibet

  > 

  > 

  > 

  > --- On *Wed, 12/30/09, Ali Nesin /<anesin at nesinvakfi.org>/* wrote:

  > 

  > 

  >     From: Ali Nesin <anesin at nesinvakfi.org>

  >     Subject: Re: [MD-sorular] Gödel'in eksiklik
  teoremi

  >     To: "tibet efendi"
  <tibetefendi at yahoo.com>

  >     Cc: "Matematik Dunyasi"
  <md-sorular at matematikdunyasi.org>

  >     Date: Wednesday, December 30, 2009, 2:52 PM

  > 

  > 

  >     Sorunu anlatacagim ama once perspektifini
  degistirmem lazim.

  > 

  >     Iki turlu teori olur dogada:

  >     1) Grup teorisi gibi, aksiyomlarini zaten tahmin
  ettigin teoriler.

  >     Bunlar genellikle sonlu sayida aksiyom
  icerirler. Oyle olmasa da

  >     en azindan recursive'dirler.

  >     2) Elinde oncelikli olarak bir teori degil
  matematiksel bir yapi

  >     olur. Ornegin (R, +, ., <, 0, 1) gibi (gercel
  sayilar yapisi).

  >     Buna dilersen exp ve sin ve cos fonksiyonlarini
  da ekleyebilirsin.

  >     Simdi bu yapida dogru olan tum onermeleri al. Bu
  bir teoridir ve

  >     elbette celiskisi olmayan bir teoridir (cunku
  teorinin

  >     onermelerini dogrulayan bir yapi vardir,
  dolayisiyla teoriden

  >     celiski cikamaz.). Ustelik herhangi bir onerme
  icin, ya bu onerme

  >     ya da bu onermenin degillemesi teoridedir. Yani
  bu tam bir

  >     teoridir. Bu teori recursive midir? Recursive
  olmasa da

  >     recursively enumerable midir? Ana soru bu. Cunku
  neyin teoride

  >     neyin teoride olmadigini bilmen lazim teorinin
  bir ise yaramasi icin.

  > 

  >     Birincisinde teoriden basliyorsun, ikincisinde
  yapidan.

  > 

  >     1) Yukardaki birinci durumdaki gibi Peano
  aritmetigini alabilirsin

  >     ya da grup teorisini alabilirsin ya da
  "theory of totally dense

  >     ordered sets without end points"i
  alabilirsin ve bu teorilerin tam

  >     olup olmadigi sorusunu sorarsin. Ilk ikisi tam
  degildir, ucuncusu

  >     tamdir.

  >     2) Ikinci durumdaki gibi bir yapi alip, bu
  yapinin teorisini

  >     aksiyomlayan sonlu, o da olmadi recursive, o da
  olmadi recursively

  >     enumerable bir aksiyom sistemi bulmak istersin.

  > 

  >     Simdi (N, +, x, <, 0, 1) yapisi (yani dogal
  sayilar yapisi) cok

  >     dogal bir yapidir. Bu yapida dogru olan
  onermeleri recursively

  >     enumerable bir bicimde yazabilir miyim? Daha
  temel bir soru: Sonlu

  >     sayida onermeyle bu teoriyi aksiyomatize
  edebilir miyim? Yani bu

  >     yapida dogru olan her onerme, onceden
  belirlenmis sonlu sayida

  >     aksiyomun bir sonucu mudur? yanit bildigin gibi
  olumsuz.

  > 

  >     Ali

  > 

  > 

  > 

  >     tibet efendi wrote:

  >     > Gödel'in eksiklik teoremi'yle ilgili kafama
  takilan bir sey var.

  >     >

  >     > Gödel'in eksiklik teoremi su:

  >     > Dogal sayilarin toplamasini ve carpmasini
  iceren "recursively

  >     enumerable" bir aksiyom sistemi, celiski
  üretmiyorsa eksik olmak

  >     zorundadir.

  >     > Yani o sistemde dogrulugu ve yanlisligi
  kanitlanamayan önermeler

  >     olmak zorundadir.

  >     >

  >     > Bu teorem neden bu kadar büyük sansasyon
  yaratmis anlamiyorum.

  >     >

  >     > 1) Gödel bunu kanitlamak icin "bu
  önerme kanitlanamaz" gibi

  >     gicik ve kendine gönderme yapan bir önerme
  yazilabilecegini

  >     gösteriyor.

  >     > Iyi de bu kendine gönderme yapan gicik
  önermeleri bir sekilde

  >     yasaklarsak, belki de sorun cözülecek.

  >     > Yani bu gicik önermeler, öyle kimsenin de
  "bunun dogrulugunu ya

  >     da yanlisligini kanitlayamazsam dünya bana
  zindan olur" diye

  >     düsündügü önermeler degildir herhalde.

  >     >

  >     > Neden bütün önermelerin dogrulugunu ya da
  yanlisligini

  >     kanitlamak bu kadar mühim? Bir örnekle acayim:

  >     >

  >     > 2) Grup teorisine bakalim. Grup teorisinde
  su cümlenin ne

  >     yanlisligini ne de dogrulugunu kanitlayabiliriz:
  "her x ve y icin

  >     xy=yx esitligi dogrudur".

  >     > Cünkü abelyen gruplar vardir, abelyen
  olmayan gruplar vardir.

  >     >

  >     > Yani grup aksiyomlari "eksik"tir.

  >     > Ama bu bizi rahatsiz etmiyor.

  >     > Neden rahatsiz etsin ki?

  >     >

  >     > Ayni sekilde diyebilmeliyiz ki:

  >     > "gödel'in gicik cümlesinin dogru
  oldugu, dogal sayilar

  >     aritmetigini iceren modeller vardir,

  >     > ama ayni sekilde o cümlenin yanlis oldugu
  dogal sayilar

  >     aritmetigini iceren modeller vardir."

  >     >

  >     > Dolayisiyla aksiyom sistemi o cümlenin
  dogrulugunu ve

  >     yanlisligini kanitlamaya yetmiyor.

  >     > Ne kadar tamamlamaya calisirsak calisalim,
  hep de eksik kalacak.

  >     > Bence bunda da bir sorun yok.

  >     >

  >     > Neden Gödel'in kaniti matematigin
  temellerini sarsiyor? Neresi

  >     sarsiyor?

  >     >

  >     > Benim göremedigim, atladigim sey nedir?

  >     >

  >     > tibet

  >     >

  >     >

  >     >

  > 
     ------------------------------------------------------------------------

  >     >

  >     >
  _______________________________________________

  >     > MD-sorular e-posta listesi

  >     > sorular at matematikdunyasi.org

  > 
     </mc/compose?to=sorular at matematikdunyasi.org>

  >     > http://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular

  > 

  >  
  
  
  
 


   

   

__________ Information from ESET NOD32 Antivirus, version
of virus signature database 4730 (20091230) __________ 

   

The message was checked by ESET NOD32 Antivirus. 

   

http://www.eset.com 

   

Bu elektronik posta ve onunla iletilen bütün dosyalar gizlidir ve
sadece göndericisi tarafindan almasi amaçlanan yetkili gerçek ya da tüzel
kisinin kullanimi içindir. Eger söz konusu yetkili alici degilseniz bu
elektronik postanin içerigini açiklamaniz, kopyalamaniz, yönlendirmeniz ve
kullanmaniz kesinlikle yasaktir ve bu elektronik postayi derhal silmeniz
gerekmektedir. SAMPAŞ bu mesajin içerdigi bilgilerin dogrulugu veya eksiksiz
oldugu konusunda herhangi bir garanti vermemektedir. Bu nedenle bu bilgilerin
ne sekilde olursa olsun içeriginden, iletilmesinden, alinmasindan ve
saklanmasindan sorumlu degildir. Bu mesajdaki görüsler yalnizca gönderen kisiye
ait olup, her zaman SAMPAŞın görüslerini yansitmayabilir. Bu e-posta bilinen
bütün bilgisayar virüslerine karsi taranmistir.  

   

This e-mail and any files transmitted with it are confidential and
intended solely for the use of the individual or entity to whom they are
addressed. If you are not the intended recipient you are hereby notified that
any dissemination, forwarding, copying or use of any of the information is
strictly prohibited, and the e-mail should immediately be deleted. SAMPAS makes
no warranty as to the accuracy or completeness of any information contained in
this message and hereby excludes any liability of any kind for the information
contained therein or for the information transmission, reception, storage or
use of such in any way whatsoever.The opinions expressed in this message may
belong to sender alone and may not necessarily reflect the opinions of SAMPAS.
This e-mail has been scanned for all known computer viruses.  

   

   



 Bu e-posta mesaji, mesajin alici kisminda belirtilmis olan kullanici icindir. Mesajin alicisi siz degilseniz dogrudan veya dolayli olarak mesaji kullanmayiniz, acmayiniz, dagitmayiniz, yazicidan dokumunu almayiniz veya herhangi bir kismini kopyalamayiniz. Yanlislikla bu mesaj size ulasmissa lutfen, siliniz ve tum kopyalarini yok ederek mesaji gonderene acilen haber veriniz. Bu mesaj icerisinde belirtilenler sadece gondericinin kisisel gorusleridir. Bu gorusler Sermaye Piyasasi Kurulu' nun (SPK) goruslerini yansitmadigi gibi, SPK' yi baglayici da degildir. Bu mesajin icerisinde ya da eklerinde yer alan bilgilerin dogrulugu, butunlugu ve guncelligi SPK tarafindan garanti edilmemektedir ve bilinen viruslere karsi kontrolleri yapilmis olarak yollanan mesajin sitenizde yaratabilecegi zararlardan SPK sorumlu tutulamaz.
This e-mail is intended solely for the use of the individual or entity to whom it is addressed. If you are not the intended addressee of this message, you should not use, open, disseminate, distribute, print or copy this e-mail. If you have received this e-mail in error, please delete it from your system and notify the sender immediately. The Capital Markets Board of Turkey (CMB) does not accept any legal responsibility whatsoever for the contents of this message. Any opinions contained in this message are those of the author and are not given or endorsed by the CMB. The CMB does not warrant the accuracy, integrity and currency of the information transmitted with this message. This message has been detected for all known computer viruses thence CMB is not liable for the occurrence of any system corruption caused by this message. 




      
-------------- sonraki blm --------------
Bir HTML eklentisi temizlendi...
URL: http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20091231/0d13715c/attachment.htm 


MD-sorular mesaj listesiyle ilgili daha fazla bilgi