Halting prediction on busy beaver type Turing machines based on information entropy

Bu tezde Busy Beaver türü Turing Makinaları için asimptotik olarak tam bir sonlanma öngörüsü öneriyoruz. Aynı zamanda farklı sonlanma öngörüsü sistemlerini karşılaştırabilmek için bir verimlilik ölçümü sunuyoruz ve son olarak geçerli Turing Makinası tanımlarını topolojik anlamda temsil edebilecek Manhattan uzaklık fonksyonu türevi bir uzaklık fonksyonuna sahip metrik bir uzay ve bu uzaydaki komşulukları tanımlıyoruz.Sonlanma öngörüsü sistemimiz, benzetim geçmişindeki bir noktada Turing makina teybinin ziyaret edilmiş kısım uzunluğunun, teyp başlığının kaymalarına oranını, simülasyon geçmişinde o nokta için bilgi yoğunluğunun bir ölçümü olarak kullanarak simülasyon geçmişinin o anı için bir sayma sürecinin üretilip üretilemeyeceğini ispatlamaya dayanmaktadır. Busy Beaver Turing Makinalarının simülasyon geçmişlerinin her noktasında zamansal konumunu takip edebiliyor olması gerektiğini göstererek, önerdiğimiz bilgi yoğunluğu ölçütünü zamansal konum takibinin mümkünlüğünü test ederek takibin imkansızlığı halini sonlanmama öngörüsü kanıtı olarak kullanıyoruz. Normal makina benzetimine çok az bir hesapsal yük ekleyerek verimli bir erken sonlanma/sonlanmama öngörüsüne ulaşabiliyoruz.