Delphi.science

Postselection on Halting and Reductions to the Halting Problem

Source: arxiv.org/abs/2611.20517

Saman Farhat, Farzad Didehvar

arXivarxiv/2611.20517Nov 16, 2026cs.CCscore 0

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…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'