Skip to main content
2 of 2
edited tags
Joel David Hamkins
  • 236.4k
  • 44
  • 777
  • 1.4k

Probability that a Turing machine is universal?

I choose a Turing machine T with n states and an input tape at random.

What can be proven about the probability P_A(n) that it is not decidable whether T will halt for a particular input? What can be proven about P_B(n) that T is universal, that means that there exists an algorithm that takes an obvious encoding of an arbitrary Turing machine A (without input tape) and transforms it into an input for my random Turing machine, so that T halts with this input if and only if A halts? In particular: Is it known that P_A(n) is strictly smaller than P_B(n) for some n?

twiz
  • 187
  • 4