Id: arxiv/2611.20517 Url: https://arxiv.org/abs/2611.20517 Tags: cs.CC, cs.LO, math.LO, quant-ph Score: 0 Title: Postselection on Halting and Reductions to the Halting Problem Domain: cs.CC Source: arxiv Authors: Saman Farhat, Farzad Didehvar Reviews: 0 Subject: cs.CC Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-16 Page: https://delphi.science/r/arxiv/2611.20517 A probabilistic Turing machine is an ordinary Turing machine that may also toss fair coins, with no limit on its running time or memory. If it always halts, it decides only computable problems. Aaronson et al. studied machines that may run forever on some coin tosses, with the answer read only from the runs that halt. Suppose the correct answer must be more than twice as likely as the wrong one. They showed that these machines decide exactly the problems solvable with a fixed list of questions about the halting problem. They asked what happens when the correct answer need only be the more…