[MD-sorular] Hesaplanabilir sayılar ve cebirsel sayılar

[tibet efendi]

Turing makinasinin ne oldugunu anlamak icin hesaplanabilirlik kavrami üzerine kafa yormak gerekiyor.
Turing makinasi nedir diye sordugunuzda herkes "efendim sonsuz bir bant var. girdiyi okuyan ve yazan, bunun ardindan kafasini bir saga bir sola hareket ettirebilen bir sey var" diye makinanin tarifine girisiler. Siz de hic bir sey anlamadiginizla kalirsiniz. Ben uzun süre ne oldugunu anlayamamistim bu tarifler yüzünden. Siz de ayni sikintiyi yasamayin diye biraz bir sey anlatacagim.

Hesaplanabilirlik ne demektir? (sezgisel olarak)
(dogal sayilardan dogal sayilara) bir fonksiyon icin hesaplanabilirlik, o fonksiyonun her dogal sayi icin aldigi degeri bulan bir algoritmanin varligidir. Yani sonlu adim sonunda bize fonksiyonun aldigi degeri söyleyecek o algoritma.

Bu tanim sezgiseldir. Cünkü her seyden önce algoritma ne demektir? Bunun matematiksel bir tanima dönüstürülmesi gerekir. Bunun bir cok yolu var.
1) hesaplanabilir fonksiyonun tümevarimsal yöntemle tanimi yapilir. (Gödel böyle yapmistir)
2) Turing makinesi yardimiyla yapilir. (Bu Turing'in yöntemi)
3) lamda-kalkül diye bir sey var. (Church böyle yapmistir)
baska yöntemler de vardir kesin.

Simdi önemli bir nokta: Bu yukaridaki 3 yöntemle tanimlanan hesaplanabilirlik kavramlarinin tipa tip ayni hesaplanabilirlik kavrami oldugu kanitlanmistir. Ve bu, Church tezi denen sey degildir.

Church tezi sunu der: bu yöntemlerden biriyle tanimladigimiz hesaplanabilirlik kavrami yukarida sezgisel olarak anlattigimiz kavramla örtüsür.

Bu Church tezi kanitlanabilir bir sey degildir. Cünkü matematiksel bir önerme degildir. Matematiksel bir cümle degildir. Matematik-ötesi mi denir meta-matematiksel mi denir öyle bir sey iste. Mantikcilar falan bu teze inanmaktadirlar. Inansaniz da inanmasaniz da bir sey degismez ya... Iste öyle bir sey.

Turing makinasina gelince: Bu makina bir kere pratikte varolabilecek bir makina degildir cünkü sonsuz hafizasi (sonsuz uzunlukta bant) vardir. Cok basit hareketler yapan bir makinadir. Cok primitif bir alettir. Ama bugünkü bilgisayarlarla yazabileceginiz her algoritmayi Turing makinasinda programlayabilirsiniz. Bu cok önemli. Bu yüzden "evrensel" turing makinasi lafi kullanilir. Yani akliniza gelebilecek her türlü matematiksel algoritmayi bu inanilmaz derecede basit alet icin programlayabilirsiniz. Turing makinasinin bantli mantli tanimini yazmiyorum onu internette her yerde bulursunuz.

Turing makinasini iyi anlamak icin bir Turing makinasi programi yazmaniz gerekir. Örnegin Turing makinasi icin dogal sayilarda toplama islemini yapan bir program yazmaya calisirsaniz makinanin ne oldugunu cok iyi anlarsiniz. Böyle bir sey yazmadan da makinayi tam anlamis saymayin bence kendinizi. Bu arada anlamasi kolay bir seydir. Bilen biri örneklerle anlatsa bir saatte anlasilabilecek bir seydir. Ama kendiniz arastirinca o bantli mantli tanimlar yüzünden kafa karisikligi yapar.

tibet



--- 26/02/10 Cum tarihinde Erdem Erdemgil <erdem.erdemgil at yahoo.com> şöyle yazıyor:

Kimden: Erdem Erdemgil <erdem.erdemgil at yahoo.com>
Konu: Re: [MD-sorular] Hesaplanabilir sayılar ve cebirsel sayılar
Kime: "md-sorular matematikdunyasi.org" <md-sorular at matematikdunyasi.org>
Tarihi: 26 Şubat 2010 Cuma, 16:31

 
Hesaplanamaz sayı var mıdır ?
Belirli bir basmakta yuvarlatılmış veya kesilmiş, sonsuz basamağa kadar elde edilememiş,
edilmesi mümkün olmayan sayı, mesela pi sayısı, bu anlamda hesaplanamaz sayı olarak mı
tanımlanıyor ?
Zaten fiziksel olarak sonsuz basamak üretmek  hiç bir makina ile mümkün değil,
en gelişmiş teknoloji ile ve ilerde de, yüzyıllar binyıllar sonra bile münkün olamaz
diye düşünüyorum.
Şu Turing makinası da nedir, basit kısa ve özlü bir açıklama yapılabilir mi ?
Ben bu MD-sorular ortamında yeni bir üyeyim,
öğrenmek için soruyorum,
yanıtlarınız için önceden teşekkürler.
Erdem Erdemgil 



From: E. Mehmet Kıral <luzumi at gmail.com>
To: Tarik Ozkanli <tarik.ozkanli at sampas.com.tr>
Cc: md-sorular at matematikdunyasi.org
Sent: Fri, February 26, 2010 4:45:21 PM
Subject: Re: [MD-sorular] Hesaplanabilir sayılar ve cebirsel sayılar


 Insanlar pi sayisinin ondalik basamaklarini bilgisayar yardimiyla bulabildiklerine gore, pi de hesaplanabilir bir sayidir. Ancak cebirsel degildir.



2010/2/26 Tarik Ozkanli <tarik.ozkanli at sampas.com.tr>




Merhaba,
“Tüm hesaplanabilir sayılar aynı zamanda cebirsel sayılardır. “
Önermesinin doğruluk değeri hakkında ne söylenebilir? 
 Hesaplanabilir sayıları Turing’in makalesinde tanımladığı, bir Turing makinesinin çıktısı olarak üretilebilen sayılar olarak anlıyorum.
http://en.wikipedia.org/wiki/Computable_number
 
Cebirsel sayıları ise aşağıdaki şekilde anlıyorum.
http://en.wikipedia.org/wiki/Algebraic_numbers
 Esenlikler.
 -- 
Eren Mehmet Kıral




      
-----Satır İçi Eki Var-----

_______________________________________________
MD-sorular e-posta listesi
sorular at matematikdunyasi.org
http://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular


      ___________________________________________________________________
Yahoo! Türkiye açıldı!  http://yahoo.com.tr
İnternet üzerindeki en iyi içeriği Yahoo! Türkiye sizlere sunuyor!
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: <http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20100226/d900b82d/attachment-0001.htm>