Exploring Halting Times for Unconventional Halting Schemes
Katarzyna Krzyzanska
Wolfram Summer Camp
East Amherst, NY 14051, USA
18kkrzyzanska@nardin.org
Abstract
A common issue in the study of Turing machines (TMs) is the halting problem, or whether and when a TM will cease moving. Generally, this problem has been proved to be uncomputable, though it is possible to determine halting probabilities for more specific cases. In the following study, halting probabilities were determined using two unconventional definitions of halting. The first defines halting as the point where a machine reaches a certain, prespecified step; the second defines halting as the point where cell states stop changing (though head states may still differ from step to step). Due to computational limitations, the halting probabilities for TMs with fewer head and cell states have been more thoroughly studied than for more complicated machines, but nonetheless some data has been garnered concerning those. The TMs studied ranged from two possible head states and two possible cell states to six possible head states and six possible cell states.
Keywords: Turing machines; halting problem; complexity; estimation
