TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-07

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Some undecidable languages have polynomial-size circuits

Statement

There is an undecidable language in $P / p o l y$ ; indeed, one can choose a language having constant-size circuits at every input length.

Facts & Assumptions

Given: a fixed effective enumeration $(M_{n})_{n \in N}$ of Turing machines.

[L1]

The diagonal halting problem is undecidable, by The halting problem is recognizable and undecidable.

[L2]

A $P / p o l y$ family need not be effectively constructible from its input length, by Circuit families and P/poly.

Proof

technique · direct

1.1

Let $H = {n : M_{n} (n) halts}$ and form the tally language $U = {1^{n} : n \in H}$ . A decider for $U$ would decide $H$ by mapping $n$ to $1^{n}$ , so $U$ is undecidable by [L1]. Define the binary length language $L = {x : 1^{∣ x ∣} \in U}$ . If $L$ were decidable, its decider restricted to $1^{n}$ would decide $U$ ; hence $L$ is undecidable.

L1givenconstruct

2.1

For each $n$ , choose $C_{n}$ to be the constant-one circuit if $1^{n} \in U$ , and the constant-zero circuit otherwise. Then for every $x \in {0, 1}^{n}$ , $C_{n} (x) = 1$ exactly when $x \in L$ . The circuits have constant size, and their non-effective length-by-length choice is permitted by [L2].

L2step 1.1construct

3.1

Thus $L$ is both undecidable and recognized by a polynomial-size circuit family.

step 1.1step 2.1∎

Depends on

Used by

Unary circuits for an undecidable language are not uniformly generated Counterexample
Polynomial-size circuits imply a uniform polynomial-time generator False statement

Dependency tree · two levels

10 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Arora and Barak, Computational Complexity: A Modern Approach (standard reference, not scraped)
Lance Fortnow, Counting Complexity (standard reference, not scraped)