Problema di arresto probabilistico

Question

Sono uno studente di fisica e matematica che lavora attraverso il testo di Nielsen & Chuang su calcolo e informazioni quantistiche. Non ho molta esperienza nella teoria CS, quindi alcuni di questi esercizi mi confondono:

Supponiamo di numeriamo le macchine probabilistiche di Turing e definiamo la funzione di arresto probabilistica $ h_p (x) $ essere 1 se macchina $ x $ si ferma sull'ingresso di $ x $ con probabilità almeno 1/2 e 0 se macchina $ x $ si ferma sull'ingresso di $ x $ con probabilità inferiore a 1/2. Mostra che non esiste una macchina per Turing probabilistica che può produrre $ h_p (x) $ con probabilità di correttezza rigorosamente maggiore di 1/2 per tutti $ x $.

Sono sicuro che dovremmo presumere che esista una macchina da Turing probabilistica che lo fa, e quindi mostrare che possiamo risolvere il problema di arresto deterministico usando questa macchina, ottenendo così una contraddizione. Tuttavia, non ho idea di come passare da questa macchina per Turing probabilistica a una deterministica.