Otomata Teorisi Nedir? | Otomatlar ve Biçimsel Diller

Otomata Teorisi Nedir: Bütün Problemleri Çözen Sihirli Yöntem

İkinci derece denklemleri çözmeyi biliriz. Sayılar yuvarlaksa hemen görülebilir zaten. Kesirliyse ya da köklüyse? Ya da daha kötüsü, çözüm yoksa?

Bu denklemlerle bir süre uğraştıktan sonra her birini tek tek çözmenin pek de iyi bir fikir olmadığı sonucuna varırız. Biraz uğraşarak, kareye tamamlama yöntemiyle, kök deltalı o meşhur formülü elde edebiliriz.

Formül bize çözüm varsa çözümü verdiği gibi, çözüm yoksa da (yani delta negatifse) bunu bildirir. Ayrıca sayıların büyük, küçük, rasyonel, irrasyonel olmalarından etkilenmez.

Buradaki düşünceyi çok, ama çok genelleştirip, tüm denklemlere uygularsak, belki ünlü Alman matematikçi Hilbert’in 1900 yılında ortaya attığı ve 20. Yüzyıl matematiğine yön veren problemleri anlayabiliriz: Genel, mekanik, her durumda uygulanabilecek ve sonlu sayıda adımdan sonra sonuç verecek bir prosedür var mıdır? Bugünkü adıyla algoritmadan bahsettiğini anlamak çok zor değil.

1930’larda bu problem İngiliz matematikçi Alan Turing tarafından enine boyuna incelenmiş. (Enigma’yı çözen Turing mi? diye soruyorsanız, bravo, ta kendisi!) Ortada daha bilgisayar yokken, tamamen teorik olarak, bir bilgisayarın yapabileceği ve yapamayacağı işlemler tanımlanmış. Bugün hala onun anısına bu teorik modele Turing Makinası diyoruz. Sonsuz uzunlukta bir şerit ve üzerine 0 ya da 1 yazıp silebilecek bir kafadan ibaret. İlginç olan şu ki, bugünkü bilgisayarların yaptığı her şeyi bu teorik modeldeki bilgisayar da yapabiliyor.

Başta sorduğumuz sorunun cevabı maalesef negatif. Her zaman sonuç veren bir yöntem yok. Bunun ispatı da 20. Yüzyıl matematik ve bilgisayar bilimlerinin bir nevi başyapıtı: Öyle bir yöntem olduğunu varsayarsak, o yöntemle çözülemeyecek bir problem tasarlanabiliyor. Elbette ki ispatın ayrıntıları oldukça teknik.

Bu bahsettiğim konular genelde bilgisayar mühendisliği bölümlerinin 3 veya 4. sınıfındaki “Hesaplama Kuramı” ya da “Otomatlar ve Biçimsel Diller” başlıklı dersinde anlatılır. Turing Makinaları ve çözümsüz problemler dışında, gramerler, bunlardan türetilebilecek diller, makul (yani polinom) ve kabul edilemeyecek kadar uzun (yani üstel) sürede sonuç veren algoritmalar da en önemli alt başlıklardandır.

Uzun yıllar verdiğim bu dersin notlarını, Ekim 2020’de yayınlanan “Automata, Formal Languages and Turing Machines” adlı kitabımda bulabilirsiniz. Yakında Türkçesi de çıkacak olan kitap, tamamen öğrenci odaklı olup, her bir kavram iyice anlaşıldıktan sonra o kavramlar arasındaki ilişkileri kurmakta, kendin yapmadan öğrenemezsin prensibiyle öğrenciye basitten başlayıp adım adım karmaşıklaşan çok sayıda çözümlü ve cevaplı egzersiz sunmaktadır.

Dr. Öğr. Üyesi Emre SERMUTLU

 



İlk yorum yapan olun

Bir Cevap Yazın