Postselection on Halting and Reductions to the Halting Problem
Source: arxiv.org/abs/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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.20517
curl -X POST /api/v1/records/arxiv/2611.20517/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.20517/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'