Abstract:
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.