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.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    17
    References
    1
    Citations
    NaN
    KQI
    []