[MD-sorular] DUZELTME Turing makinasi

tibet efendi tibetefendi at yahoo.com
9 Oca 2009 Cum 20:30:19 EET


"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/2c4ef4ce/attachment.htm 


MD-sorular mesaj listesiyle ilgili daha fazla bilgi