Turing makinesi (İngilizce Turing machine), karmaşık matematiksel hesapların belirli bir düzenek tarafından yapılmasını sağlayan hesap makinesi.
Tarihçe
Karmaşık hesapların belirli bir düzenek tarafından yapılıp yapılamayacağı, 20. yüzyılın başlarında büyük bir tartışma konusu olmuştu. Öteden beri el ile veya zihinden yapılan hesaplamalar çok zaman almakla birlikte, birçok hatayı da beraberinde getiriyordu. Tüm bu tartışmalar sürerken, 1936 yılında, ünlü matematikçi Alan M. Turing "Saptama Problemi Hakkında Bir Uygulamayla Birlikte Hesaplanabilir Sayılar" (İngilizce On computable numbers, with an application to the Entscheidungsproblem) isimli bir makalesini yayınladı. Makalesinde teorik ve matematiksel temellere dayalı sanal bir makineden bahseden Turing, her türlü matematiksel hesabın bu sanal makineyle yapılabileceğini iddia ediyordu. Turing’in 1950 yılında yayınlanan "Hesaplama Mekanizması ve Zeka" (İngilizce Computing Machinery and Intelligence) isimli ikinci makalesi ise, makineler ve zekayla ilgili birçok tartışmalı konuya cevap niteliğindeydi. İşte bu makalelerde sözü geçen sanal makine daha sonraları bu adla isimlendirildi.
Çalışma prensibi
Bu tablo, Turing makinesinin çalıştırdığı algoritmadır. Turing makinesi, her adımda
- O anda kafanın görmekte olduğu sembolü okur.
- Geçiş tablosunda okuduğu sembol ve o anki durumunu içeren bir girdi arar:
- Eğer öyle bir girdi bulursa, yazılacak sembolü yazar veya kafasını hareket ettirir ve yeni duruma geçer. Makine, yeni durum ve kafanın okuduğu yeni sembol ile çalışmaya devam edecektir.
- Eğer öyle bir girdi bulamaz ise, durur.
Örnek
Örneğimizdeki Turing makinesi sembol havuzu (yani alfabe) olarak {'B', '1'} kullanmaktadır. Bu makineni amacı, verilen girdinin en sağına 1 ekleyip girdinin en soluna geri dönmektir.
Bu amaca ulaşabilmek için, {'d0', 'd1', 'd2'} şeklinde üç durum kullanacağız. Bu durumların geçiş tablosu ise şu şekilde olacak:
Güncel durum | Okunan simge | İşlem | Yeni durum |
---|---|---|---|
d0 | 1 | Sağa git | d0 |
d0 | B | 1 yaz | d1 |
d1 | 1 | Sola git | d1 |
d1 | B | Sağa git | d0 |
Makine, ilk başta d0 durumunda olacak. Bu tabloya bakarak görebiliriz ki, d2 son durum olacak ve makinenin kafası şu işlemi yapacak:
- 1 sembolünü gördükçe sağa doğru gidecek.
- B sembolünü gördüğü an (yani girdinin en sağına ulaştığında) o sembol yerine 1 yazacak.
- Yazma işlemi bitince 1 sembolü gördükçe sola gidecek.
- B sembolünü gördüğü an (yani girdinin en soluna ulaştığında) bir adım sağa gidecek ki girdinin ilk harfine doğru bakıyor olsun.
Birkaç denemeyle bu makinenin istediğimiz işlemi yaptığını görebiliriz.
Değişik Turing makineleri
Anlatılan Turing makinesi, yapılabilecek en basit makinedir. Bunu şu şekilde geliştirebiliriz:
- Beş girdili geçiş tablolu Turing makinesi: bu makine, bir sembol okuyup gerekli işlemi yaptıktan sonra hem yeni bir sembol yazıp hem de aynı anda kafasının yerini değiştirebilir.
- Birkaç şerit okuyuculu Turing makinesi: bu makine, birkaç şeride aynı anda okuyup yazabildiği için paralel işlem yapabilir.
Buna ek olarak, anlatılan Turing makinesi belirlenimci (determinist) bir makinedir, başka bir deyişle aynı girdi için her zaman aynı çıktıyı üretir:
- Belirlenimsiz Turing makinesi (İngilizce Non Deterministic Turing machine), çalışmaya başlamadan önce şeride rastgele bir sembol dizisi yazar, bu aşamaya tahmin etme aşaması (İngilizce: guessing stage) denir. NP problem grubunun tanımı bu makine ile yapılabilir.
- Kâhinli Turing makinesi (İngilizce Oracle Turing machine), anlatılan donanımlara ek olarak bir kahin içerir. Turing makinesi, bu kahine bir soru sorabilir, kahin de bu soruyu cevaplayacaktır. NP complete problem indirgemesi bu makine ile yapılabilir.
Kaynakça
Dış bağlantılar
- Turing'in adı geçen makalesinin taranmış orijinali[]
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Turing makinesi Ingilizce Turing machine karmasik matematiksel hesaplarin belirli bir duzenek tarafindan yapilmasini saglayan hesap makinesi Turing makinesi temsili gorunum TarihceKarmasik hesaplarin belirli bir duzenek tarafindan yapilip yapilamayacagi 20 yuzyilin baslarinda buyuk bir tartisma konusu olmustu Oteden beri el ile veya zihinden yapilan hesaplamalar cok zaman almakla birlikte bircok hatayi da beraberinde getiriyordu Tum bu tartismalar surerken 1936 yilinda unlu matematikci Alan M Turing Saptama Problemi Hakkinda Bir Uygulamayla Birlikte Hesaplanabilir Sayilar Ingilizce On computable numbers with an application to the Entscheidungsproblem isimli bir makalesini yayinladi Makalesinde teorik ve matematiksel temellere dayali sanal bir makineden bahseden Turing her turlu matematiksel hesabin bu sanal makineyle yapilabilecegini iddia ediyordu Turing in 1950 yilinda yayinlanan Hesaplama Mekanizmasi ve Zeka Ingilizce Computing Machinery and Intelligence isimli ikinci makalesi ise makineler ve zekayla ilgili bircok tartismali konuya cevap niteligindeydi Iste bu makalelerde sozu gecen sanal makine daha sonralari bu adla isimlendirildi Calisma prensibiBu tablo Turing makinesinin calistirdigi algoritmadir Turing makinesi her adimda O anda kafanin gormekte oldugu sembolu okur Gecis tablosunda okudugu sembol ve o anki durumunu iceren bir girdi arar Eger oyle bir girdi bulursa yazilacak sembolu yazar veya kafasini hareket ettirir ve yeni duruma gecer Makine yeni durum ve kafanin okudugu yeni sembol ile calismaya devam edecektir Eger oyle bir girdi bulamaz ise durur OrnekOrnegimizdeki Turing makinesi sembol havuzu yani alfabe olarak B 1 kullanmaktadir Bu makineni amaci verilen girdinin en sagina 1 ekleyip girdinin en soluna geri donmektir Bu amaca ulasabilmek icin d0 d1 d2 seklinde uc durum kullanacagiz Bu durumlarin gecis tablosu ise su sekilde olacak Guncel durum Okunan simge Islem Yeni durumd0 1 Saga git d0d0 B 1 yaz d1d1 1 Sola git d1d1 B Saga git d0 Makine ilk basta d0 durumunda olacak Bu tabloya bakarak gorebiliriz ki d2 son durum olacak ve makinenin kafasi su islemi yapacak 1 sembolunu gordukce saga dogru gidecek B sembolunu gordugu an yani girdinin en sagina ulastiginda o sembol yerine 1 yazacak Yazma islemi bitince 1 sembolu gordukce sola gidecek B sembolunu gordugu an yani girdinin en soluna ulastiginda bir adim saga gidecek ki girdinin ilk harfine dogru bakiyor olsun Birkac denemeyle bu makinenin istedigimiz islemi yaptigini gorebiliriz Degisik Turing makineleriAnlatilan Turing makinesi yapilabilecek en basit makinedir Bunu su sekilde gelistirebiliriz Bes girdili gecis tablolu Turing makinesi bu makine bir sembol okuyup gerekli islemi yaptiktan sonra hem yeni bir sembol yazip hem de ayni anda kafasinin yerini degistirebilir Birkac serit okuyuculu Turing makinesi bu makine birkac seride ayni anda okuyup yazabildigi icin paralel islem yapabilir Buna ek olarak anlatilan Turing makinesi belirlenimci determinist bir makinedir baska bir deyisle ayni girdi icin her zaman ayni ciktiyi uretir Belirlenimsiz Turing makinesi Ingilizce Non Deterministic Turing machine calismaya baslamadan once seride rastgele bir sembol dizisi yazar bu asamaya tahmin etme asamasi Ingilizce guessing stage denir NP problem grubunun tanimi bu makine ile yapilabilir Kahinli Turing makinesi Ingilizce Oracle Turing machine anlatilan donanimlara ek olarak bir kahin icerir Turing makinesi bu kahine bir soru sorabilir kahin de bu soruyu cevaplayacaktir NP complete problem indirgemesi bu makine ile yapilabilir Kaynakca TURING A M 1 Ekim 1950 I COMPUTING MACHINERY AND INTELLIGENCE Mind LIX 236 433 460 doi 10 1093 mind lix 236 433 ISSN 1460 2113 Stanford Felsefe Ansiklopedisi 24 Eylul 2018 3 Mayis 1998 tarihinde kaynagindan arsivlendi Erisim tarihi 20 Subat 2021 Dis baglantilarTuring in adi gecen makalesinin taranmis orijinali olu kirik baglanti