Durma Problemi ve Resmi İspatlar
Bu bölümde, bir önceki bölümün konusuyla uzaktan yakından ilgili bir alana dolambaçlı bir yoldan gidiyoruz. Bir ifadeyi ayrıştıran ve anında ifadeyi değerlendiren bir sürecin nasıl yazılacağını gördük. Bu bölümde, ifadeler için dilbilgisinin uzantılarını esasen “gerçek” bir programlama diline genişleterek ele alıyoruz ve bu durumda, dildeki dizelerin tüm ilginç niteliklerini değerlendirmek için bir işlev yazmanın artık mümkün olmadığı sonucuna varıyoruz.
Özellikle, gelişigüzel bir programın sonlu mu yoksa sonsuz bir hesaplamayı mı çağrıştırdığını belirlemek mümkün değildir. Bunu yaparak, maliyet gibi bazı pratik sınırlamaları göz ardı ederken, programlama dillerinin ve bilgisayarların bazı temel sınırlamalarını keşfediyoruz.
Bazı programcılar muhtemelen çözülemeyecek sorunları çözmeye çalıştılar ve bazıları da çözülemez olduğu kanıtlanan sorunları çözmeye çalıştılar. Pratik programcıya bu tür problemlerin varlığını öğrenmesi tavsiye edilir.
Doğruluğunu kontrol etmek şöyle dursun, bir programın yürütülmesinin sona erip sonlanmadığını mekanik olarak kontrol edememek, yalnızca doğru programlar yazmak için daha fazla nedendir. Ne kadar zor olursa olsun, bunu, programı doğruluğunun kanıtının bir taslağı ile el ele tasarladığımız iyi organize edilmiş bir şekilde programlar geliştirerek yapmaya çalışıyoruz. Kanıtı nadiren tüm ayrıntılarıyla veririz, ancak her adımda çok dikkatli davranarak, ihtiyaç duyulduğunda tam kanıtı verebileceğimize ikna oluruz.
Durma Problemi
Bir ifadeyi ayrıştırmak ve değerlendirmek için kullanılan programa tercüman denir. Bu program yürütülürken her türlü dönüştürme gerçekleşir: bir karakter dizisi bir sayıya dönüştürülür, / operatörü bir div uygulamasına dönüştürülür vb.
Programı bir tamsayı döndüren ve global bir girdi dosyası üzerinde çalışan bir prosedür olarak yazdık. Ayrıca, bir karakter dizgesini argüman olarak alan ve dizge tarafından temsil edilen tamsayı değerini döndüren bir fonksiyon olarak da yazabiliriz.
Tercüman, tanımlayıcıları ve bunların “anlamlarını” içeren bir çiftler tablosu tutabilir; yapı sırasında x tanımlayıcısını 3 tamsayısıyla birleştiren çifti ekler.
Yorumlanacak dizgede r her çağrıldığında, tanım aranır ve eklenir. Ancak şimdi, sonlandırılmama riskiyle karşı karşıyayız: tercümanımızın tüm girdilerde sonlandırdığı açık değildir. Örnekte, x = 0’a ve 29 sonucuna götüren 42 r çağrısı olacaktır.
Ancak, x’in başlangıç değeri – 1 olarak değiştirilirse yorumlayıcı sonsuza kadar döngüye girer. Parametresi, yorumlayıcımızın sonlandığı bir dizge olduğunda doğru döndüren h gibi bir boole işlevine sahip olmak yararlı olacaktır. O zaman şöyle bir şey yazabiliriz.
Ve E yorumlayıcısının s giriş dizisinde sonlandırılmasını garanti eder. s’nin seçildiği dil yeterince kısıtlıysa, h’yi yazmak çok zor değildir. Dil özyineleme içeriyorsa, daha zor hale gelir. Aslında, h’nin var olduğunu varsayarak ve ardından bir çelişki türeterek h fonksiyonunu yazmanın imkansız olduğunu gösteriyoruz.
Halting Problem nedir
Halting ne demek
Turing makinesi Nedir
Turing Makinesi PDF
Turing makinesi Örnek Sorular
Turing makinesi çeşitleri
Turing makinesi örnekleri
I işlevinin tanımını ve I çağrısını içeren dizeyi düşünün. I’in gövdesi, varsayımsal h işlevimizin çağrılmasını içerir. h(J)’nin doğru olduğu bulunursa, o zaman sonsuz bir döngüye girer ve hiçbir zaman 7 döndürmez, aksi takdirde, 3 değerini döndürür. Parametresi I olan h işlevi çağrılır; tanımlayıcıların tanımlarını saklayan yazışma tablosunu tanımladığımız şekilde, I gerçekten de bir dizgeye bağlıdır.
Burada çelişkimiz var: h(f) = -,h(f). h fonksiyonunu yazmanın imkansız olduğu sonucundan kaçamayız. Bir noktada hile yaptık: çelişkiyi elde etmek için kullandığımız dizgeye h’nin tanımını dahil etmeliydik çünkü ben h’yi çağırıyorum.
Aynı dilde yazılan herhangi bir fonksiyonun sona erip sonlanmayacağını belirleyen bir fonksiyon programlamak mümkün değildir. Tercüman yazma fikrinden hoşlanmıyorsanız ve tüm ispatı daha geleneksel matematiksel terminolojide hecelemeyi tercih ediyorsanız, bu yapılabilir. Bu çok zor bir iş. Durma probleminin çözülemezliğini ilk kanıtlayan Thring tarafından yapıldı.
Mantık ve Boole İfadeleri
Önceki bölümlerde özellikle programların doğruluk ispatlarında ve gramerler ile diller arasındaki ilişkiyi kurmak için birçok boole ifadesi yazarken bulduk kendimizi. VLSI devrelerini tartıştık ve bu devrelerin mantıksal ifadeleri değerlendirmek için nasıl kullanılabileceğini gördük. Bu bölümde, boole ifadelerine ve bunların nasıl manipüle edileceğine daha yakından bakacağız.
Programların (veya bu nedenle başka herhangi bir şeyin) doğruluğuna kendimizi ikna etmek için boolean ifadelerden yapılmış kanıtlara güveniyorsak, boolean ifadelerle çalışma konusunda yetkin olduğumuzdan emin olsak iyi olur. ispat çok inandırıcı olmayacaktır yani ispat olmayacaktır.
Bahsettiğimiz bu mantıksal ifadeler ne tür nesnelerdir? Muhtemelen matematiksel mantıkta karşılaştığınız önermelere ve yüklemlere benziyorlar. Bununla birlikte, benzerlik yanıltıcıdır ve aslında boole ifadelerimiz cebirsel ifadelere veya analizden bildiğiniz şekliyle aritmetik ifadelere çok daha yakındır. Önce mantığa bir göz atalım.
Önermeler ve yüklemler, belirli sözdizimsel kısıtlamaları karşılayan dizelerdir. Bu dizelere iyi biçimlendirilmiş formüller denir. Örneğin, p 1\ (q V r) ve x < y + 3 iyi biçimlendirilmiştir ve x < (y = 7) ve x(> değildir. Daha sonra, wff’ler (onlara atıfta bulunulduğu şekliyle) türetilebilir olarak adlandırılanlar ve olmayanlar olarak ikiye ayrılır.
Türetilebilir dizelerin tanımı özyinelemeli bir tanımdır:
• bazı dizgiler türetilebilir olarak verilmiştir (aksiyomlar),
• yeni türetilebilir dizilerin nasıl değiştirilebileceğine dair bazı kurallar verilmiştir.
zaten türetilebilir dizilerden yapılandırılmıştır (çıkarım kuralları),
• başka dizi türetilemez.
Çıkarım kuralına bir örnek Modus Ponens’tir: p türetilebilir bir dizeyse ve p :: q türetilebilir bir dizeyse, q türetilebilir bir dizedir. Bu kural genellikle yazılır.
Bir mantıkta türetilebilen dizeler ile bir dilbilgisi tarafından oluşturulan dil arasındaki benzerliğe dikkat edin. Mantıkçıların ilgilendiği sorulardan biri de türetilebilir wff’lerin “ilginç” kümesinin ne olduğudur.
Mantıkta çok kullanılan bir aygıta model veya anlam denir ve wff’ler kümesinden {true,false} boole değerleri kümesine kadar bir işlevdir. Böyle bir işlevin tanımlanması, sayılar gibi dizeler veya mantıksal değerler dışındaki kavramları içerebilir.
Anlam işlevi, bazı alt dizileri boole değerleri yerine bu kavramlarla eşler, böylece işlev aslında daha geniş bir etki alanına ve daha geniş bir aralığa sahiptir. Girişte kullandığımız { l , p, q} üzerindeki grameri hatırlayın. llplqlll’in türetilebilir olduğu ve IIIIPiqll’in türetilemediği bir mantığa kolayca çevrilir. Bu dizileri sırasıyla doğru ve yanlış olarak eşleyen bir model düşünülebilir.