Counterfactual Effect, the Halting Problem, and the Busy Beaver Function
1999
Using the counterfactual effect, we demonstrate that with better than 50% chance we can determine whether an arbitrary universal Turing machine will halt on an arbitrarily given program. As an application we indicate a probabilistic method for computing the busy beaver function— a classical uncomputable function. These results suggest a possibility of going beyond the Turing barrier.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
17
References
1
Citations
NaN
KQI