Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinin önemli bir kısmını oluşturan otomatlar (Automata) ve Algoritma Analizi (Algorithm analysis) çalıştırmalarının altındaki dil bilimin en temel taşlarından birisidir.1936 yılında Alan Turing tarafından ortaya atılan makine tasarımı günümüzde pekçok teori ve standardın belirlenmesinde önemli rol oynar.
Turing Makinesinin Tanımı
Basitçe bir kafadan (head) ve bir de teyp bandından (tape) oluşan bir makinedir.
Makinede yapılabilecek işlemler
- Yazmak
- Okumak
- Bandı ileri sarmak
- Bandı geri sarmak
şeklinde sıralanabilir.
Chomsky hiyerarşisi ve Turing Makinesi
Bütün teori bu basit dört işlem üzerine kurulmuştur ve sadece yukarıdaki bu işlemleri kullanarak bir işin yapılıp yapılamayacağı veya bir dilin bu basit 4 işleme indirgenip indirgenemeyeceğine göre diller ve işlemler tasnif edilmiştir.
Bu sınıflandırma yukarıdaki venn şeması ile gösterilmiştir. Aynı zamanda chomsky hiyerarşisi (chomsky hierarchy) için 1. seviye (type-1) olan ve Turing makinesi ile kabul edilebilen diller bütün tip-2 ve tip-3 dilleri yani içerk bağımsız dilleri ve düzenli dilleri kapsamaktadır. Ayrıca ilave olarak içerik bağımsız dillerin işleyemediği (üretemediği veya parçalayamadığı (parse) ) anbncn şeklindeki kelimeleri de işleyebilmektedir. Düzenli ifadelerin işleyememesi konusunda bilgi için düzenli ifadelerde pompalama savı (pumping lemma in regular expressions) ve içerik bağımsız dillerin işlemeyemesi için de içerik bağımsız dillerde pompalama savı (pumping lemma for CFG) başlıklı yazıları okuyabilirsiniz.
Turing Makinesinin Akademik Tanımı
Turing makineleri literatürde akademik olarak aşağıdaki şekilde tanımlanır:
Burada M ile gösterilen makinenin parçaları aşağıda listelenmiştir:
Q sembolü sonlu sayıdaki durumların kümesidir. Yani makinenin işleme sırasında aldığı durumardır.
Γ sembolü dilde bulunan bütün harfleri içeren alfabeyi gösterir. Örneğin ikilik tabandaki sayılar ile işlem yapılıyorsa {0,1} şeklinde kabul edilir.
Σ sembolü ile makineye verilecek girdiler (input) kümesi gösterilir. Girdi kümesi dildeki harfler dışında bir sembol taşıyamayacağı için Σ ⊆ Γ demek doğru olur.
δ sembolü dilde bulunan ve makinenin çalışması sırasında kullanacağı geçişleri (transitions) tutmaktadır.
◊ sembolü teyp bandı üzerindeki boşlukları ifade etmektedir. Yani teyp üzerinde hiçbir bilgi yokken bu sembol okunur.
q0 sembolü makinenin başlangıç durumunu (state) tutmaktadır ve dolayısıyla q0 ⊆ Q olmak zorundadır.
F sembolü makinenin bitiş durumunu (state) tutmaktadır ve yine F ⊆ Q olmak zorundadır.
Örnek Turing Makinesi
Yukarıdaki sembolleri kullanarak örnek bir Turing makinesini aşağıdaki şekilde inşa edebiliriz.
Örneğin basit bir kelime olan a* düzenli ifadesini (regular expression) Turing makinesi ile gösterelim ve bize verilen aaa şeklindeki 3 a yı makinemizin kabul edip etmediğine bakalım.
Tanım itibariyle makinemizi aşağıdaki şekilde tanımlayalım:
M = { {q0,q1} , { a } , { a,x } , { q0 a→a R q0 , q0 x→x L q1} , q0 , x , q1 }
Yukarıdaki bu makineyi yorumlayacak olursak:
Q değeri olarak {q0,q1} verilmiştir. Yani makinemizin ik idurumu olacaktır.
Γ değeri olarak { a,x } verilmiştir. Yani makinemizdeki kullanılan semboller a ve x’ten ibarettir.
Σ değeri olara {a} verilmiştir. Yani makinemize sadece a girdisi kabul edilmektedir.
δ değeri olarak iki geçiş verilmiştir { q0 a→a R q0 , q0 x→x L q1} buraadki R sağa sarma L ise sola sarmadır ve görüleceği üzere Q değerindeki durumlar arasındaki geçişleri tutmaktadır.
◊ değeri olarak x sembolü verilmiştir. Buradan x sembolünün aslında boş sembolü olduğu ve bantta hiçbir değer yokken okunan değer olduğu anlaşılmaktadır.
q0 ile makinenin başlangıç durumundaki hali belirtilmiştir.
F değeri olarak q1 değeri verilmiştir. Demek ki makinemiz q1 durumuna geldiğinde bitmektedir (halt) ve bu duruma gelmesi halinde bu duruma kadar olan girdileri kabul etmiş olur.
Yukarıdaki bu tanımı görsel olarak göstermek de mümkündür:
Yukarıdaki bu temsili resimde verilen turing makinesi çizilmiştir.
Makinemizin örnek çalışmasını ve bant durumunu adım adım inceleyelim.
Birinci adımda bandımızda aaa (3 adet a) yazılı olduğunu kabul edelim ve makinemizin bu aaa değerini kabul edip etmeyeceğini adım adım görelim. Zaten istediğimiz de aaa değerini kabul eden bir makine yapabilmekti.
Yukarıdaki ilk durumda bant üzerinde beklenen ve kabul edilip edilmeyeceği merak edilen değerimiz bulunuyor. Makinemizin kafasının okuduğu değer a sembolü. Makinemizin geçiş tasarımına göre q0 halinde başlıyoruz ve a geldiğinde teybi sağa sarıp yine q0 durumunda kalmamız gerekiyor.
Yeni durumda kafamızın okuduğu değer banttaki 2. a harfi ve bu durumda yine q0 durumundayken teybi sağa sarıp yine q0 durumunda kalmamız tasarlanmış
3. durumda kafamızın okuduğu değer yine a sembolü olmakta ve daha önceki 2 duruma benzer şekilde q0 durumundayken a sembolü okumanın sonucu olarak teybi sağa sarıp q0 durumunda sabit kalıyoruz.
4. adımda teypten okuduğumuz değer boşluk sembolü x oluyor. Bu değer makinemizin tasarımında q1 durumuna gitmemiz olarak tasarlanmış ve teybe sola sarma emri veriyoruz.
Makinenin son durumunda q1 durumu makinenin kabul ve bitiş durumu olarak tasarlanmıştı ( makinenin tasarımındaki F kümesi) dolayısıyla çalışmamız burada sonlanmış ve giriş olarak aaa girdisini kabul etmiş oluyoruz.
2. Örnek
Hasan Bey’in sorusu üzerine bir örnek makine daha ekleme ihtiyacı zuhur etti. Makinemiz {a,b} sembolleri için çalışsın ve ilk durum olarak bandın en solunda başlayarak bantta bulunan sembolleri silmek için tasarlansın. Bu tasarımı aşağıdaki temsili resimde görülen otomat ile yapabiliriz:
Görüldüğü üzere makinemizde 4 durum bulunuyor, bunlardan en sağda olan h durumu bitişi (halt) temsil ediyor. Şimdi bu makinenin bir misal olarak “aabb” yazılı bir bantta silme işlemini nasıl yaptığını adım adım izah etmeye çalışalım.
Aşağıda, makinenin her adımda nasıl davranacağı bant üzerinde gösterilmiş ve altında açıklanmıştır. Sarı renge boyalı olan kutular, kafanın o anda üzerinde durduğu bant konumunu temsil etmektedir.
Netice olarak Hasan Bey’in sorusuna temel teşkil eden ve örneğin q1 üzerindeki döngülerden birisi olan b/a,R geçişi, banttan b okunduğunda banta a değerini yaz manasındadır.
Yine bu yazıya yapılan yorumlarda sorulan bir sorunun cevabını aşağıdaki bağlantıda çözdüm. Soru, eşit a ve b içeren Turing makinesinin tasarımı idi, bağlantıya tıklayarak okuyabilirsiniz.
http://www.bilgisayarkavramlari.com/2010/11/19/esit-a-ve-b-bulunduran-turing-makinesi-ornegi/
Cok aciklayici ve guzel olmus. Emegine saglik adim adim anlatmissin
Gerçekten güzel bir yazı. Derse girememiştim burdan okudum anladım. Fakat turing makinası bence girdi olarak X’i (elmas sembolü) yani boş bant değerini de kabul ediliyor. Çünkü onla da işlem yapılmış ki state diyagramında bu gözüküyor (2. geçiş). Girdi olarak a değil de a,x şeklinde olması gerekmiyor mu?
Yukarıdaki örnek turing makinesi, girdi olarak her adımda banttan tek bir sembol okumakta. Dolayısıyla girdi kısmı her zaman için tek sembolden oluşuyor. okun sağında bulunan değer ise banta geri yazılan değeri temsil ediyor.
Sizin yorumunuzdan anladığım kadarıyla siz oku durum geçişi olarak yorumlamışsınız. Bu yanlış. örneğin a -> a , R şeklindeki bir değer, daha önce okuduğun a değerinden sonra a değeri gelirse sağa sar şeklinde anlaşılmamalı! Bu satırın anlamı banttan a değerini oku ve banta a değerini geri yaz ve bandı sağa sar anlamına gelmektedir.
Yukarıdaki örneklerde banttan okunan değer aynen banda geri yazılmıştır.
Yukarıdaki örneklerde banta yazılan değerin birönemi olmadığı için bu yorumu yapmakta haklısınız. Birazdan ikinci bir örnek ekleyip banta bir değer yazılması halinde Turing makinesinin nasıl çalıştığını göstermeye çalışırım. Örneğin bantta yazan bilgileri silen bir turing makinesinin nasıl çalışıtığını yukarıdaki yazıya ekleyelim.
Başarılar
Evet yeni eklenen kısım olayı mükemmel biçimde açıklamış.
Doğrusu ben M = { {q0,q1} , { a } , { a,x } , { q0 a→a R q0 , q0 x→x L q1} , q0 , x , q1 } kısmındaki x’ten bahsetmiştim. Yani bunun yerine
M = { {q0,q1} , { a,x } , { a,x } , { q0 a→a R q0 , q0 x→x L q1} , q0 , {x, elmas} , q1 } şeklinde olması gerekmiyor mu? Sonuçta makina elmas sembolünü de (yani x) kabul edip ona göre bir karar verebilyor.
2.süper olmuş…ama bence biraz daha geniş bir turing makinesi tasarlanıp gösterilebilir.mesela;bir girdnin kopyasını yapıp,daha sonra girilen girdiyi silip,kopyasından girilen girdinin 2katı (mesela girdi ab ise ab’yi kopyalayıp bu kopyadan abab üreten) şeklinde çıkı veren turing makinesi yapılsa muazzam olur…
Tarik Bey istediginiz sey odev mi yoksa? Cok nokta atisi yapmissiniz !
yok ödev değil…pek otomatadan ödev aldığımız söylenemez.sadece bir anlık aklıma gelen bir fikirdi.
geçen gün otururken böyle bir tane de aklıma geldi onu yaptım ama sorduğum soruyu yapamadım.öyleki; herhangi bir string bir turing makinesi tarafından önce baştan bir elemanı sonra sondan bir elemanı ve bu string elemanı bitene kadar kopyalayıp sonra bu kopyadan tekrar ana stringi veren turing makinesi…yani diyelimki;abaabbb girilen bir string şu şekilde kopyalanmalı:
Abaabbb
AbaabbB
ABaabbB
ABaabBB
ABAabBB
ABAaBBB
ABAABBB
şeklinde kopyalansın sonra da sırayla stringi kopyalasın…yaptım bunu.ama yapana kadar da bayağı zorlandım..
tek kelimeyle harika bir anlatım. paylaşımınız için teşekkürler
çok iyi anlatım. çok teşekkürler.
peki, acaba eşit sayıda a ve b içeren kelimeleri tanıyan turing makinesi nasıl yapılır ?
şimdi bu soru iki türlü anlaşılabilir. Kolay olanı anbn şeklinde a ve b harflerinin sırayla gelmesi. yani n tane a harfinin n tane b harfinden önce gelmesi. Tabi bir de eşit sayıda a ve b olması ve bunların karışık dizilimde olması mümkün.
Yani ilk durumda aaabbb şeklindeki kelimeleri kabul ederken ikinci durumda aabbab şeklindeki kelimeleri de kabul etmesini bekleyebiliriz.
ilk durum için basitçe kelimenin başından bir a sildiğimizde, kelimenin sonundan da bir b silicez. Dolayısıyla a ve b harfleri aynı anda biterse eşitler, şayet birisi önce biterse eşit değiller diyeceğiz.
ikinci durum ise biraz daha zor, kelimenin başından bir harf silip (örneğin a) sonra tersi olan harfi (bu durumda b) kelimenin yine başından ilk gördüğümüz durumda silmemiz gerekiyor. Ancak bu silme işlemini kaydırarak yapmamız gerekiyor.
Örnek üzerinden anlatacak olursam :
-abaaaabbbb- şeklinde bir kelime olsun:
a ve hemen sonra kelimede gelen ilk b siliniyor
—aaaabbbb- halini alıyor ve devam ediyoruz:
—-aaabbbb- şimdi bir a sildik ve bir de b silmemiz gerek. Makinemiz ilk b’yi bulup silecek:
—-aaa-bbb- fakat görüldüğü üzere kelimenin içinde boşluk oldu bunu düzeltmek için kaydırıyoruz:
—-aaabbb– ve böylece devam ediyor.
Burada boşluk oluşması ve kaydırma probleminin çözümü için ilave bir sembol kullanılabilir. Örneğin c sembolü kullanacak olalım. ilk silmeden sonra
-ccaaaabbbb- şeklinde ilk a ve b silindiler
-cccaaacbbb- şeklinde ikinci silme gerçekleşti ve bu şekilde devam ediyoruz. Ta ki bütün kelime c olana kadar. Şayet b veya a önce biterse o zaman eşit değil diyebiliriz.
Yukarıda, iki problemin de çözümünü anlattım ama kolay olanının makinesini çizip adım adım yukarıdaki yazıya ekleyeceğim. Eh zor olanını da artık siz yaparsınız 🙂
sorunuzun cevabını aşağıdaki bağlantıda yayınladım.
http://www.bilgisayarkavramlari.com/2010/11/19/esit-a-ve-b-bulunduran-turing-makinesi-ornegi/
başarılar
peki esit sayida ve siralari karisik sekilde verilen a,b,c leri iceren turing makinesi nasil yapilir.?
gerçekten çok güzel anlatılmış yarın 1 de sınavım var anlamamıştım iyi geldi:D:D
bir teyp üzerinde 3 hücreye a harfi yazılıdır.turing makinesinden istenen bu hücrelere b harfi yazmasıdırgeçiş fonksiyonlarını ve geçişleri yazın diye bir soru var bana yardımcı olursanız sevinirim
Sorunuzun cevabı basitçe, teypte a görülmesi halinde teybe b yazılması ve teypteki karakterlerin bitmesi halinde de makinenin durmasıdır.
M = { {q0,q1} , { a } , { a,b,x } , { q0 a→b R q0 , q0 x→x L q1} , q0 , x , q1 }
Yukarıdaki makinenin başlangıç durumu q0, bitiş durumu q1’dir. a sembolü gördüğü sürece b yazmakta ve teybi sağa sarmaktadır. yıldız sembolü ile teypteki karakterler bitince son olarak sola sararak durmaktadır.
Sorunuzda 3 sembol bulunduğu kabulü var. Bu sembollerin sayısının kontrol edilmesi istenmemiş. Sadece okuyup üzerine b yazıyoruz.
Buna göre makinenin çalışması :
-aaa- olarak teyp başlar | q0, a->b R , işlemi sonucunda q0'da kalır ve teyp kayar -baa- | tekrar q0'da olduğu için q0, a->b R , işlemi sonucunda q0'da kalır ve teyp kayar -bba- | tekrar q0'da olduğu için q0, a->b R , işlemi sonucunda q0'da kalır ve teyp kayar -bbb- | okunan değer x olduğu için q0'dan q1 durumuna geçeriz. (q0 x→x L q1 gereği) -bbb- | q1 durumunda makinemiz durur ve çalışma biter.başarılar
şimdi anlatım güzel olmuş fakat benim anlayamdığım konu şu bu makine ne işe yarıyor ve nasıl kelimeleri üretiyor?
Turing makinesi anlaşılmaz o bir yaşam biçimidir 🙂
Espiri bir yana, kullandığınız bütün programlama dilleri birer Turing Makinesidir. Turing makineleri, günümüzde üretimden çok tüketim için kullanılır. Yani kelime üretmez ama daha çok verilen kelimelerin verilen kurallara uygun olduğunu denetler ve anlamlarına göre işler yapar. Aynı bir programlama dilinde bir derleyiciye bir kaynak kodu verdiğinizde çalışması gibi. Elbette makine ters anlamda kelime üretmek için de kullanılabilir ancak bu çok daha karmaşık bir yazının konusu.
Kabaca bilgilenmek için von neumann makinesi başlıklı yazıyı aşağıdaki bağlantıda yayınlamıştım:
http://www.bilgisayarkavramlari.com/2010/10/05/von-neumann-makinesi/
Belki başlangıç için iyi olabilir. Yine de anlaşılmazsa yorum yazmanız durumunda daha fazla bilgi vermeye çalışırım. Ayrıca nacizane görüşüm bu tip konuların en azından otomata teorisi (automata theory) alınmadan anlaşılmasının güç olduğu.
Başarılar
mod2=0 ı tanıyan bir turing makinesi tasarlayınız. yardımcı olursanız cok sevınırım acıl lazım sınavım var 🙁
teyp bandındaki boşlukların amacı ne,ne işe yarıyorlar açıklayabilir misiniz?
Boşluklar henüz kayıt yapılmamış alanlardır. Genelde teybe kayıt yapılmadığında tamamını boş kabul edebiliriz. Kayıtlar sırasında ise kayıt alanının başı ve sonunu anlamak için kullanılırlar.