Decryption-Capable Analog Machines: Bounded-State Conditions under Which Key Search Implies Universal Computation

In plain language

The researchers wanted to know when a machine that can break codes must also be able to run any computer program. They showed that any decryption device whose key space can grow beyond three hundred and one bits must solve search problems that no brute‑force computer within the universe’s limits can handle. They also proved that a fixed‑oscillator machine, no matter how fast, stays in a finite‑state class that cannot perform universal computation. Think of it like trying to lift a car with a single rubber band: the effort required quickly becomes impossible.

Restated for a non-expert reader; the original wording follows. 1 statement(s) without support in the text were removed. Still uses some technical language.

In the paper's words

Analog and hybrid physical machines — oscillator networks, photonic solvers, and resonant parametron arrays — increasingly demonstrate search and optimization behavior that resembles the dynamics of codebreaking machines. A standing folk conjecture holds that any machine able to decrypt messages is necessarily a general-purpose computer, because decryption requires the same search dynamics as universal computation. The gap this paper addresses is that the conjecture has never been stated with explicit resource conditions, so it cannot be confirmed or refuted for realistic analog hardware.

The abstract, verbatim, and its opening sentence is the claim. Every line below is quoted from the text.

Numbers it reports

1. Any decryption machine whose keyspace can be enlarged past 301 bits is, under (A1)–(A3), solving search problems that no enumerative machine within the universe's operation budget can solve by brute force — which sharpens why its computational class matters.

   from 4.1 Universal budgets and the cost of brute-force decryption

2. Together they establish that (i) enumeration is excluded as the mechanism of any fast decryptor, (ii) keyspaces beyond 301 bits exceed all enumerative capacity within the universal operation budget, and (iii) any fixed-oscillator machine, however fast on its task family, sits in a finite-state class strictly below universality.

   from 5. Results

3. The engineering pathway for building and verifying such machines is measured by [3], whose Analog Design Bench runs 50 transistor-level tasks by 17 chip designers across 15 agent configurations and 2,250 attempts with two-hour budgets, finding that "the difficulty lies in electrical closure, not syntax: recorded legality rejections account for 1.1% of attempts," that DeepSWE scores between 67 and 70 accompany analog pass rates from 31% to 78%, and that additional time adds 14.0–20.0 points from two to six hours.

   from 2. Background and Related Work

4. For the MNIST-scale networks used in [8]'s validation, take $n = 784$ (one oscillator per input pixel, a natural choice for a 784-dimensional input; we state this as an assumption about the architecture scale): $$S(784) = 2^{3136}\ \text{states},\qquad m = 3136\ \text{readable bits}.$$ This is a large but finite state space: the machine computes only functions on at most 3136 bits of working memory and cannot, for example, decide $\{a^n b^n\}$ for arbitrary $n$.

   from 4.3 Bounded-state impossibility: no bounded analog machine is Turing-complete

5. For the programmable hardware Theorem 1's conditional requires, the first binding constraint is analog design and verification effort: [3] measures that current coding agents reach analog pass rates of 31% to 78% on transistor-level tasks with two-hour budgets, that the difficulty lies in electrical closure rather than syntax (legality rejections are 1.1% of attempts), and that extending budgets from two to six hours adds 14.0–20.0 points — so automated assistance exists but does not close programmable-coupling designs without expert iteration.

   from 7. Practical Implications and Engineering Pathways

6. Second, parallel key search: under the assumption of 1 kg processors at $10^9$ ops s$^{-1}$, a 2-hour 128-bit search needs $4.73\times 10^{25}$ processors and mass $4.73\times 10^{25}$ kg (Derivation 7) — infeasible by roughly seventeen orders of magnitude even before energy; under the nanofabricated density implicit in [12], mass $3.4\times 10^8$ kg and energy $9.5\times 10^{17}$ J remain the binding figures.

   from 7. Practical Implications and Engineering Pathways

How it is done

1. We derive that exhaustive 128-bit key search at $10^9$ operations per second requires $3.40\times 10^{29}$ s sequentially, that the critical key length against a universal operation budget of $5.24\times 10^{90}$ is $n^{*}=301$ bits, and that a bounded machine with $m$ bits of readable state cannot decide any function requiring more than $m$ bits of working memory, so no bounded analog machine is Turing-complete regardless of its search power.

   from Abstract

2. Our contributions are: A formal model of a decryption machine (Section 3) and a conditional theorem that unbounded-keyspace, programmable decryption capability implies the ability to decide any language in NP, hence NP-hard search (derived in Section 4).

   from 1. Introduction

3. The thermodynamic floor for such arithmetic is Landauer's bound, which [10] states as $kT\ln 2$ joules per erased bit and uses to argue that iterative stochastic weight updates in deep learning "essentially perform massive amounts of information erasure in every training epoch," generating an entropy tax that must be radiated away.

   from 2. Background and Related Work

4. This paper is a formal analysis with explicit arithmetic; it performs no experiment, simulation, or measurement.

   from 3. Methods

What would falsify it

1. The gap this paper addresses is that the conjecture has never been stated with explicit resource conditions, so it cannot be confirmed or refuted for realistic analog hardware.

   from Abstract

2. We prove conditionally that unbounded-keyspace, programmable decryption capability implies NP-hard search, and we exhibit a counterexample to the strong conjecture: a fixed oscillator Ising machine with 4-bit phase readout is a finite-state system and decrypts only fixed-width keys.

   from Abstract

3. A bounded-state impossibility result: a physical machine with $m$ bits of readable state computes only functions realizable with $m$ bits of working memory, so no bounded analog machine is Turing-complete; we exhibit the fixed oscillator Ising machine with 4-bit phase readout as an explicit counterexample to the strong conjecture (Section 4).

   from 1. Introduction

Where the claim stops

1. What the theorems do and do not claim.

   from 6. Discussion

2. Theorem 1 is conditional on the programmability assumption (A2), and this is the paper's weakest link.

   from 6. Discussion

3. If the compilation overhead is exponential in $n$ for some verifier family, Theorem 1 fails for those instances and the DM's search class drops below NP-hard.

   from 6. Discussion

Where to read

1. Abstract238 words · 1 min
2. 1. Introduction556 words · 2 min
3. 2. Background and Related Work1,035 words · 5 min
4. 3. Methods445 words · 2 min
5. 4. Analysis1,595 words · 7 min
6. 5. Results244 words · 1 min
7. 6. Discussion1,022 words · 4 min
8. 7. Practical Implications and Engineering Pathways852 words · 4 min
9. 8. Conclusion271 words · 1 min
10. Provenance and AI Involvement240 words · 1 min