Super-tasks, accelerating Turing machines and uncomputability

DOI10.1016/J.TCS.2003.12.007MaRDI QIDQ1434371zbMATH OpenOpenAlexWikidataFDO

Authors Oron Shagrir

Publication date 4 August 2004

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2003.12.007

zbMATH Keywords

Accelerating Turing machinesHalting problemSuper-taskThomson's paradox

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• scientific article; zbMATH DE number 1869997
• A note on accelerated Turing machines
• Hypercomputation and the Physical Church‐Turing Thesis
• Supertasks do not increase computational power
• X-machines and the halting problem: Building a super-turing machine

Cites work

• Energy conservation and supertasks
• scientific article; zbMATH DE number 1189126 (Why is no real title available?)
• scientific article; zbMATH DE number 47306 (Why is no real title available?)
• scientific article; zbMATH DE number 497572 (Why is no real title available?)
• scientific article; zbMATH DE number 1869997 (Why is no real title available?)
• scientific article; zbMATH DE number 1909823 (Why is no real title available?)
• scientific article; zbMATH DE number 1909830 (Why is no real title available?)
• Infinite time Turing machines
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Systems of Logic Based on Ordinals^†

Cited in

(11)

• Supertasks do not increase computational power
• The case for hypercomputation
• Assaying supertasks
• The collapse of supertasks
• A note on accelerated Turing machines
• scientific article; zbMATH DE number 1189126 (Why is no real title available?)
• The applicability of \$-calculus to solve some Turing machine undecidable problems
• scientific article; zbMATH DE number 1869997 (Why is no real title available?)
• Accelerating machines: a review
• Superefficiency from the vantage point of computability
• X-machines and the halting problem: Building a super-turing machine

This page was built for publication: Super-tasks, accelerating Turing machines and uncomputability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1434371)