Busy beaver türü Turing makinalarında bilgi entropisine dayalı sonlanma öngörüsü

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.