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

Abstract

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.

In this thesis we mainly propose a new asymptotically complete halting predictor for Turing Machines of Busy Beaver type which is defined by T.Rado in 1962. Also we propose an efficiency measure to benchmark different halting predictors and finally we propose a topological representation for space of valid Turing Machines as a metric space with a Manhattan like distance metric allowing us to define a neighborhood between Turing Machines.Our predictor uses the ratio of tape space explored to cycles taken during a point in simulation history as a measure of information density for that moment of simulation, which allows us to predict the unconstructability of a counting process in terms of number of cycles occurred till that point. We show that a halting Busy Beaver Turing Machine has to have the ability to keep track of its temporal position at each point of its simulation; and we construct a non-halting predictor using mentioned information density measure to show inability to track temporal position.Our method predicts non-halting of Busy Beaver Turing Machines by incurring negligible computational overhead to the regular simulation, while obtaining results very early on simulation; even for complicated machine configurations where conventional automated non-halting proving is ineffective or unfeasible.