[MD-sorular] DUZELTME Turing makinasi

[Ali Nesin]

Su yaziya bakmanizi oneririm:
http://www.matematikdunyasi.org/arsiv/PDF/05_4_67_71_GODEL.pdf

Ilginc bir yazidir.

A.

 

  _____  

From: md-sorular-bounces at matematikdunyasi.org
[mailto:md-sorular-bounces at matematikdunyasi.org] On Behalf Of tibet efendi
Sent: Friday, January 09, 2009 8:30 PM
To: barýþ uðurcan; Matematik Dunyasi
Subject: Re: [MD-sorular] DUZELTME Turing makinasi

 


"bos kelimeyi hesaplamak" yerine "bos kelimeye karar vermek" demem daha
dogru olurdu. 

Cünkü hesaplamak, Turing makinalarinda fonksiyonlar icin kullaniliyor.
f girdi alfabesiyle olusturulabilecek kelimeler kümesinden turing
makinasinin alfabesiyle olusturulabiliecek kelimeler kümesine bir fonksiyon
olsun.
Bir turing makinasi x girdisi aldiginda yazip yazip sonunda imlecin solunda
f(x) ciktisini birakiyorsa o turing makinasi f fonksiyonunu hesapliyor
denir.

Benim yazdigim soru. "bos kelimenin karakteristik fonksiyonunu hesapliyor"
seklinde okunursa dogru oluyor. 
Ama dedigim gibi "bos kelimeye karar vermek" daha güzel bir anlatim.

Bir turing makinasinin bir kelimeye karar vermesi, o kelimeyi girdi olarak
aldiginda loop'a girmemesidir. Baska bir deyisle eninde sonunda durmasidir.
Yani soruya olumlu ya da olumsuz ama mutlaka bir yanit vermesidir.
Bir kelimeye karar vermesi ile o kelimenin karakteristik fonksiyonunu
hesaplamasi ayni sey degildir ama esdegerdir. Yani birini yapan turing
makinasi kolaylikla digerini de yapabilecek sekilde modifiye edilebilir.

Bos kelime konusuna gelince. Bos kelime derken bildigimiz, genelde epsilonla
tarif edlien bos kelimeden bahsediyorum.

Yazdiklariniz dogru.

Benim bahsettigim problem yazdiklarinizla ilintili.

Problemlerin zorluklari su sekilde sirali:
Diagonal problemi < genel durma problemi (halting problem) < benim yazdigim
bos kelime problemi

Diagonal problemi de sudur: Turing makinalarinin kendi gödel-kodlarina karar
verip vermediklerine karar veren bir turing makinasi yapilabilir mi?

Bunun yanitinin olumsuz oldugundan hareketle halting problemin yanitinin da
olumsuz oldugu kanitlaniyor. Ondan hareketle de benim sorumun yanitinin
olumsuz oldugu kanitlaniyor.

Ben sorunun cevabini biliyordum. Ilginc buldugum icin sordum.
Cok ilginc bir konu.

Gödel'in aksiyomatik sistemlerle ilgili ünlü kaniti bu konularla yakindan
ilgiliymis.

tibet



--- On Fri, 1/9/09, barýþ uðurcan <barisevren19 at yahoo.com> wrote:

From: barýþ uðurcan <barisevren19 at yahoo.com>
Subject: [MD-sorular] DUZELTME Turing makinasi
To: "md" <md-sorular at matematikdunyasi.org>
Date: Friday, January 9, 2009, 10:12 AM

bir onceki (asagidaki) mesajdaki kitap kralin yeni usu I olacak (II degil).

baris

  _____  

From: barýþ uðurcan <barisevren19 at yahoo.com>
To: tibetefendi at yahoo.com; md <md-sorular at matematikdunyasi.org>
Sent: Friday, January 9, 2009 7:08:59 PM
Subject: Re: [MD-sorular] Turing makinasi

tabii burda diger bir soru hesaplanabilmenin ne demek oldugu.  roger penrose
un kralin yeni usu II kitabinin evrensel turing makinasiyla ilgili bolumunde
hesaplananamamayi turing makinasinin verilen kodu sonlu adimda yerine
getirememesi olarak tanimliyordu yanlis hatirlamiyorsam.  daha sonra da
verilen tum temel turing makinalarinin bir islemi sonlu zamanda
gerceklestirip gerceklestirmeyecegini bulabilen bir evrensel turing
makinasinin olup olmadigini arastiriyordu.  hatta olmadiginin ispatini,
irrasyonellerin sayilabilir olmadigini gosterirken de kullanilan, cantor un
dioganal yontemini kullanarak yapiyordu...bir bakin isterseniz. bu arada
mesajinizdaki "bos" un ne anlama geldigini anlamadim. mesaji da o kelimeyi
yok sayarak cevapladim.

iyi calismalar,

baris

 

  _____  

From: tibet efendi <tibetefendi at yahoo.com>
To: Matematik Dunyasi <md-sorular at matematikdunyasi.org>
Sent: Friday, January 9, 2009 3:41:00 AM
Subject: [MD-sorular] Turing makinasi


Herhangi bir Turing makinasinin Gödel kodu girdi olarak verildiginde bize o
makinanin bos kelimeyi hesaplayip hesaplayamadigini hesaplayan bir Turing
makinasi yapilabilir mi?

 

 

 

_______________________________________________


MD-sorular e-posta listesi


sorular at matematikdunyasi.org


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

 

-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20090109/f0d80651/attachment.htm