Anasayfa » MATEMATİK HER YERDE » Turing Makineleri, Hesaplanabilirlik ve Durma Problemi

Turing Makineleri, Hesaplanabilirlik ve Durma Problemi

Alan Mathison Turing, (1912-1954) İngiliz matematikçi, bilgisayar bilimcisi ve kriptolog

Alan Turing 1936’da hesaplamanın matematiksel modelini kurdu. Bu modelde, günümüzde Turing makinesi olarak adlandırılan soyut bir makine vardır.

Alan Turing’in bilgisayar biliminin temellerini atarken tanımladığı soyut Turing makinelerinin çalışma ilkesi gayet basittir. Makine sonsuz uzunlukta olduğu varsayılan bir şeridin üzerine yazılmış girdileri okur ve işler, çıktıları da yine bu şeridin üzerine yazar. Şerit, her biri sadece tek bir sembol içeren ya da boş olan karelere bölünmüştür. Makinenin kafası her seferinde sadece bir kareyi okuyabilir. Okuduğu veriyi işledikten sonra o karedeki sembolü silerek yeniden yazabilir ya da hiçbir şey yapmayabilir.

Herhangi bir algoritmayı uygulayacak Turing makinesi kurmak mümkündür. Bu sebeple algoritma kavramının matematiksel tanımı olarak Turing makineleri kullanılır.

Bilgisayar bilimindeki temel kavramlardan biri hesaplanabilirliktir. En genel anlamıyla bir soruyu çözebilme yetisini ifade eder. Bir sorunun hesaplanabilirliği, o soruyu çözmek için kullanabilecek bir algoritmanın varlığıyla yakından ilişkilidir.

Alan Turing, 1936 yılında hesaplanabilirlikle ilgili temel bir sorunun “karar verilemez” olduğunu ispatladı. “Durma problemi” olarak adlandırılan bu problem, herhangi bir girdiyi işleyen herhangi bir bilgisayar programının eninde sorunda durup durmayacağını söyleyecek genel bir algoritma olup olmadığını sorar.

Bir algoritmayı uygulayacak bir Turing makinesi kurduğunuzu ve girdiyi sonsuz uzunluktaki bandın üzerine yazıp makineye verdiğinizi düşünün. Verileri okuyup işlemeye başlayan makine bir süre sonra durup size cevabı mı verir, yoksa sonsuza kadar çalışmaya devam mı eder?

Bu sorunun cevabını verecek genel bir algoritma var mıdır?

Alan Turing durma probleminin karar verilemez olduğunu, yani herhangi bir iş için üretilmiş bir Turing makinesine herhangi bir girdi verildiğinde makinenin eninde sonunda durup durmayacağını söyleyebilecek genel bir algoritma olmadığını ispatladı.

Durma probleminin karar verilemez olması, bir Turing makinesinin durup durmayacağının hiçbir zaman bilinemeyeceği anlamına gelmez. Örneğin makineye verilen tek komut “Okuduğun veriyi sil ve dur” ise makinenin ilk okuduğu veriden sonra duracağı açıktır. Ya da makineye verilen tek komut “Sıfır yaz ve bir birim sağa kay” ise makinenin sonsuz uzunluktaki bant üzerinde hiç durmadan sürekli sıfır yazarak ilerleyeceği açıktır.

Ancak Turing’in ispatı makinenin durup durmayacağını belirlemenin tek yolunun makineyi çalıştırıp beklemek olduğunu söyler. Eğer makine bir noktada durup size cevabı verirse durduğunu bilirsiniz. Ancak bir süre önce çalıştırdığınız makine hâlâ verileri işleyip çalışmaya devam ediyorsa bir süre sonra durup durmayacağını kesin olarak söyleyemezsiniz.

Dolayısıyla durma problemi “karar verilemez” ya da “hesaplanamaz”dır.

Konu ile ilgili aşağıdaki videoya da göz atmak isteyebilirsiniz.

Konu ile ilgili bir başka yazımıza göz atmak isterseniz:
https://www.matematiksel.org/bilgisayarlarin-cozmesi-imkansiz-problem-durma-problemi/

Kaynak: Dr. Mahir E. Ocak; Cevabı Bulunamayacak Fizik Soruları – TÜBİTAK Bilim ve Teknik Dergisi

Matematiksel

Paylaşmak Güzeldir

Yazıyı Hazırlayan: Sibel Çağlar

Avatar
Kadıköy Anadolu Lisesi, Marmara Üniversitesi, ardından uzun süre özel sektörde matematik öğretmenliği, eğitim koordinatörlüğü diye uzar gider özgeçmişim… Önemli olan katedilen değil, biriktirdiklerimiz ve aktarabildiklerimizdir bizden sonra gelenlere... Eğitim sisteminin içinde bulunduğu çıkmazı yıllarca iliklerimde hissettikten sonra, peki ama ne yapabilirim düşüncesiyle bu web sitesini kurmaya karar verdim. Amacım bilime ilgiyi arttırmak, bilimin özellikle matematiğin zihin açıcı yönünü açığa koymaktı. Yolumuz daha uzun ve zorlu ancak en azından deniyoruz.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

This site uses Akismet to reduce spam. Learn how your comment data is processed.