pith. sign in

arxiv: 2604.17285 · v1 · submitted 2026-04-19 · 💻 cs.CC

Metastability-Containing Turing Machines

Johannes Bund , Amir Leshem , Moti Medina This is my paper

Pith reviewed 2026-05-10 05:50 UTC · model grok-4.3

classification 💻 cs.CC
keywords metastabilityTuring machinesmetastable closurecomputabilitycomplexityuniversal Turing machine
0
0 comments X

The pith

The metastable closure of Turing machines is non-computable in general.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper examines Turing machines that must handle inputs containing uncertain bits that could settle to either 0 or 1. It establishes that producing the full set of possible outputs over all such resolutions, called the metastable closure, is impossible for arbitrary machines. The proof follows from the fact that this task encodes undecidable questions. For machines running in exponential time, even a single uncertain bit renders the closure computation EXPTIME-complete. Polynomial-time machines admit efficient closure computation only when the number of uncertain bits stays logarithmic, but the problem jumps to coNP-complete once the number of undefined bits grows without bound. The authors also construct a universal Turing machine that computes the closure for any time-bounded machine while incurring at most exponential overhead and remaining realizable in hardware.

Core claim

We prove that in general the metastable closure of a Turing Machine is non-computable. Then we discuss cases where the meta-stable closure is computable: For EXPTIME problems, we prove that resolving even a single uncertain bit is EXPTIME-complete. In contrast, we prove that for polynomial time problems, the meta-stable closure is polynomial time computable for a logarithmic number of uncertain bits, but coNP-complete, when the number of undefined inputs is arbitrary. Finally, we describe a hardware-realizable Universal Turing Machine that computes the metastable closure of any given bounded-time Turing Machine with at most an exponential blowup in time.

What carries the argument

Metastable closure: the function that returns every possible output a Turing machine can produce when each uncertain input bit is replaced by every possible stable 0/1 combination.

If this is right

  • Resolving even one uncertain bit for an EXPTIME problem is EXPTIME-complete.
  • The metastable closure of a polynomial-time machine is computable in polynomial time when the number of uncertain bits is logarithmic.
  • The metastable closure of a polynomial-time machine becomes coNP-complete once the number of uncertain bits is allowed to grow arbitrarily.
  • A hardware-realizable universal Turing machine exists that computes the metastable closure for any bounded-time machine with at most exponential time overhead.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The hardness results suggest that metastability containment inherits the same computational barriers already known for ordinary decision problems.
  • Practical hardware systems may need to restrict the number of uncertain bits to logarithmic scale to retain efficient closure computation.
  • The universal-machine construction indicates that bounded-time metastability handling can be off-loaded to a single reusable hardware block at exponential cost.
  • The same closure idea could be applied to other models such as finite automata or circuit families to derive analogous computability thresholds.

Load-bearing premise

Uncertain inputs can be modeled by exhaustively enumerating all possible 0/1 resolutions without further constraints on signal timing.

What would settle it

An algorithm that computes the metastable closure for every Turing machine and every choice of uncertain bits would yield a decider for the halting problem.

Figures

Figures reproduced from arXiv: 2604.17285 by Amir Leshem, Johannes Bund, Moti Medina.

Figure 1
Figure 1. Figure 1: Example execution of TCMUX, where n = 4, s = 11u0 and x = x0 . . . x15. Each step shows the tape content after executing the For-loop in line 1. for one round. A CMUX on single bits a, b, s ∈ T can be implemented with a few gates in natural logic, as follows; [FK17] CMUX(a, b, s) := oru(andu(a, notu(s)), andu(b, s), andu(a, b)). (1) We denote TM that can simulate an (n: 1)-CMUX, by TCMUX. Intuitively, the … view at source ↗
Figure 2
Figure 2. Figure 2: The lattice for ⪯. In Kleene’s ternary logic, the basic operands and, or, and not (maybe together with the constants {0, 1}) are extended to their MC versions, which we denote by andu, oru and notu (see [PITH_FULL_IMAGE:figures/full_fig_p025_2.png] view at source ↗
read the original abstract

Metastability is a spurious mode of operation in digital signals, where an electrical signal fails to settle into a stable state within a specified time, leading to uncertainty and potentially failing downstream hardware. A system that computes the closure over all possibilities, given an uncertain input, is called a Metastability-containing system. While prior work has addressed metastability-containing systems in the context of combinational and clocked circuits, state machines, and logic formulas, its implications for general-purpose computation remain largely unexplored. In this work, we study the metastability-containing systems within an abstract computational model: The Turing Machine. This approach allows us to investigate the computational limits and capabilities of Turing Machines operating under uncertain inputs. Specifically, we prove that in general the metastable closure of a Turing Machine is non-computable. Then we discuss cases where the meta-stable closure is computable: For EXPTIME problems, we prove that resolving even a single uncertain bit is EXPTIME-complete. In contrast, we prove that for polynomial time problems, the meta-stable closure is polynomial time computable for a logarithmic number of uncertain bits, but coNP-complete, when the number of undefined inputs is arbitrary. Finally, we describe a hardware-realizable Universal Turning Machine that computes the metastable closure of any given bounded-time Turing Machine with at most an exponential blowup in time.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper defines the metastable closure of a Turing machine as the set of all outputs obtained by resolving uncertain (metastable) input bits in every possible 0/1 combination. It proves that this closure is non-computable in general, that computing it for EXPTIME machines with even one uncertain bit is EXPTIME-complete, that it is in P for polynomial-time machines with a logarithmic number of uncertain bits but coNP-complete for an arbitrary number, and that there exists a hardware-realizable universal Turing machine computing the closure of any bounded-time machine with at most exponential time overhead.

Significance. If the results hold, the work provides the first complexity-theoretic characterization of metastability containment for general-purpose computation, extending prior circuit- and logic-level results. The explicit UTM construction with bounded overhead and the sharp complexity thresholds (P vs. coNP vs. EXPTIME) are technically substantive and could guide the design of reliable hardware that tolerates metastable signals.

minor comments (2)
  1. The abstract contains the typo 'Universal Turning Machine' (should be 'Turing'). Ensure the full manuscript and any diagrams use consistent terminology for 'metastable closure' versus 'meta-stable closure'.
  2. The model of uncertain inputs is defined via exhaustive quantification over 0/1 resolutions; a brief remark on whether this interacts with the standard multi-tape or single-tape TM conventions (e.g., head movement on unresolved symbols) would aid readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our work and the recommendation for minor revision. The referee's description accurately captures the key contributions regarding the non-computability of the metastable closure in general, the complexity results for EXPTIME and P cases, and the hardware-realizable UTM construction.

Circularity Check

0 steps flagged

No significant circularity; standard complexity reductions

full rationale

The paper establishes non-computability of the metastable closure via reduction to the halting problem, EXPTIME-completeness for single-bit resolution on EXPTIME machines, P-time computability for log uncertain bits on P machines via exhaustive path simulation, coNP-completeness for arbitrary bits via universal quantification, and an explicit UTM construction with exponential overhead. All steps are self-contained proofs or constructions that do not reduce to self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations; prior work on circuits is cited only for context and is not invoked to justify the TM results. The derivation chain is independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The work introduces the concept of metastable closure applied to TMs, relying on standard mathematical axioms of computation without additional free parameters or invented physical entities.

axioms (1)
  • standard math Standard axioms of computability theory and complexity classes like P, EXPTIME, coNP
    The paper uses these to classify the problems.
invented entities (1)
  • Metastable closure no independent evidence
    purpose: To represent the set of all possible outputs given uncertain inputs
    Defined in the paper as the system that computes the closure over all possibilities.

pith-pipeline@v0.9.0 · 5533 in / 1503 out tokens · 61165 ms · 2026-05-10T05:50:35.771085+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [1]

    2012 , publisher=

    Digital logic design: a rigorous approach , author=. 2012 , publisher=

    work page 2012

  2. [2]

    , title =

    Turing, Alan M. , title =. Proceedings of the London Mathematical Society , volume =. 1936 , doi =

    work page 1936

  3. [3]

    American Journal of Mathematics , volume =

    Church, Alonzo , title =. American Journal of Mathematics , volume =. 1936 , publisher =

    work page 1936

  4. [4]

    Information Processing Letters , volume=

    On the complexity of detecting hazards , author=. Information Processing Letters , volume=. 2020 , publisher=

    work page 2020

  5. [5]

    IEICE Trans

    On the B-ternary logic function-A ternary logic considering ambiguity , author=. IEICE Trans. Inf. & Syst. , volume=

    work page

  6. [6]

    2014 , publisher=

    Theory of Computational Complexity , author=. 2014 , publisher=

    work page 2014

  7. [7]

    2009 , publisher=

    Computational complexity: a modern approach , author=. 2009 , publisher=

    work page 2009

  8. [8]

    Christian Ikenmeyer and Balagopal Komarath and Christoph Lenzen and Vladimir Lysikov and Andrey Mokhov and Karteek Sreenivasaiah , title =. J. 2019 , url =. doi:10.1145/3320123 , timestamp =

    work page doi:10.1145/3320123 2019

  9. [9]

    Small Hazard-Free Transducers , booktitle =

    Johannes Bund and Christoph Lenzen and Moti Medina , editor =. Small Hazard-Free Transducers , booktitle =. 2022 , url =. doi:10.4230/LIPIcs.ITCS.2022.32 , timestamp =

    work page doi:10.4230/lipics.itcs.2022.32 2022

  10. [10]

    1997 , isbn =

    Michael Sipser , title =. 1997 , isbn =

    work page 1997

  11. [11]

    1952 , publisher=

    Introduction to metamathematics , author=. 1952 , publisher=

    work page 1952

  12. [12]

    14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , pages =

    Ikenmeyer, Christian and Komarath, Balagopal and Saurabh, Nitin , title =. 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , pages =. 2023 , volume =. doi:10.4230/LIPIcs.ITCS.2023.74 , annote =

    work page doi:10.4230/lipics.itcs.2023.74 2023

  13. [13]

    Journal of the ACM (JACM) , volume=

    The design and use of hazard-free switching networks , author=. Journal of the ACM (JACM) , volume=. 1957 , publisher=

    work page 1957

  14. [14]

    Marino , title =

    Leonard R. Marino , title =. 1981 , url =. doi:10.1109/TC.1981.6312173 , timestamp =

    work page doi:10.1109/tc.1981.6312173 1981

  15. [15]

    , journal=

    Marino, Leonard R. , journal=

    work page

  16. [16]

    , title =

    Huffman, David A. , title =. Journal of the ACM , volume =. 1957 , pages =

    work page 1957

  17. [17]

    2013 Design, Automation & Test in Europe Conference & Exhibition (DATE) , pages=

    Metastability challenges for 65nm and beyond; simulation and measurements , author=. 2013 Design, Automation & Test in Europe Conference & Exhibition (DATE) , pages=. 2013 , organization=

    work page 2013

  18. [18]

    Ninth International Symposium on Asynchronous Circuits and Systems, 2003

    Fourteen ways to fool your synchronizer , author=. Ninth International Symposium on Asynchronous Circuits and Systems, 2003. Proceedings. , pages=. 2003 , organization=

    work page 2003

  19. [19]

    Unger , title =

    Stephen H. Unger , title =. 1995 , url =. doi:10.1109/12.391185 , timestamp =

    work page doi:10.1109/12.391185 1995

  20. [20]

    IEEE Transactions on Computers , volume =

    Stephan Friedrichs and Matthias F. IEEE Transactions on Computers , volume =

    work page

  21. [21]

    2020 , url =

    Johannes Bund and Christoph Lenzen and Moti Medina , title =. 2020 , url =. doi:10.1109/TC.2019.2939818 , timestamp =

    work page doi:10.1109/tc.2019.2939818 2020

  22. [22]

    Hopcroft and Jeffrey D

    John E. Hopcroft and Jeffrey D. Ullman , title =. 1979 , isbn =

    work page 1979

  23. [23]

    Synchronizer-Free Digital Link Controller , journal =

    Johannes Bund and Matthias F. Synchronizer-Free Digital Link Controller , journal =. 2020 , url =. doi:10.1109/TCSI.2020.2989552 , timestamp =

    work page doi:10.1109/tcsi.2020.2989552 2020

  24. [24]

    Johannes Bund and Matthias F. 26th. 2020 , url =. doi:10.1109/ASYNC49171.2020.00013 , timestamp =

    work page doi:10.1109/async49171.2020.00013 2020

  25. [25]

    Metastability Tolerant Computing , booktitle =

    Ghaith Tarawneh and Matthias F. Metastability Tolerant Computing , booktitle =. 2017 , url =. doi:10.1109/ASYNC.2017.9 , timestamp =

    work page doi:10.1109/async.2017.9 2017

  26. [26]

    Goto , title =

    M. Goto , title =. J. Inst. Elec. Eng. of Japan , volume =. 1949 , pages =

    work page 1949

  27. [27]

    Metastability-Aware Memory-Efficient Time-to-Digital Converters , booktitle =

    Matthias F. Metastability-Aware Memory-Efficient Time-to-Digital Converters , booktitle =. 2017 , url =. doi:10.1109/ASYNC.2017.12 , timestamp =

    work page doi:10.1109/async.2017.12 2017

  28. [28]

    Stephan Friedrichs and Attila Kinali , title =. 2017. 2017 , url =. doi:10.1109/ISVLSI.2017.65 , timestamp =

    work page doi:10.1109/isvlsi.2017.65 2017

  29. [29]

    Fischer , title =

    Nicholas Pippenger and Michael J. Fischer , title =. J. 1979 , url =. doi:10.1145/322123.322138 , timestamp =

    work page doi:10.1145/322123.322138 1979

  30. [30]

    2021 , url =

    Stasys Jukna , title =. 2021 , url =. doi:10.1137/20M1355240 , timestamp =

    work page doi:10.1137/20m1355240 2021

  31. [31]

    2012 , publisher=

    Ryan Williams and Luca Trevisan , title =. 2012 , publisher=

    work page 2012

  32. [32]

    Ginosar , journal=

    R. Ginosar , journal=. 2011 , volume=

    work page 2011

  33. [33]

    Hu and J

    W. Hu and J. Oberg and A. Irturk and M. Tiwari and T. Sherwood and D. Mu and R. Kastner , journal =. 2012 , volume =

    work page 2012

  34. [34]

    and Mazloom, Bita and Mysore, Shashidhar and Chong, Frederic T

    Tiwari, Mohit and Wassel, Hassan M.G. and Mazloom, Bita and Mysore, Shashidhar and Chong, Frederic T. and Sherwood, Timothy , title =. SIGARCH Comput. Archit. News , issue_date =. 2009 , pages =

    work page 2009

  35. [35]

    2023 , url =

    Johannes Bund and Matthias F. 2023 , url =. doi:10.1109/TVLSI.2023.3311178 , timestamp =

    work page doi:10.1109/tvlsi.2023.3311178 2023

  36. [36]

    Near-optimal metastability-containing sorting networks , booktitle =

    Johannes Bund and Christoph Lenzen and Moti Medina , editor =. Near-optimal metastability-containing sorting networks , booktitle =. 2017 , url =. doi:10.23919/DATE.2017.7926987 , timestamp =

    work page doi:10.23919/date.2017.7926987 2017

  37. [37]

    Balagopal Komarath and Nitin Saurabh , title =. Inf. Process. Lett. , volume =. 2020 , url =. doi:10.1016/J.IPL.2020.105980 , timestamp =

    work page doi:10.1016/j.ipl.2020.105980 2020

  38. [38]

    Bund, Johannes , title =

    work page

  39. [39]

    2021 , url =

    Chuxiong Lin and Weifeng He and Yanan Sun and Bingxi Pei and Pavan Kumar Chundi and Zhigang Mao and Mingoo Seok , title =. 2021 , url =. doi:10.1109/JSSC.2020.3036856 , timestamp =

    work page doi:10.1109/jssc.2020.3036856 2021