--- id: "2026-09-11-medvedev-logic-undecidable" url: "https://postcutoff.com/e/2026-09-11-medvedev-logic-undecidable/" as_of: "2026-11-13T13:49:00+01:00" date: "2026-09-11" date_precision: day category: science importance: 3 confidence: high status: [Event confirmed, Awaiting review] verification: Lean-verified sources: 2 editor: human editor human_review: null version: "2026-10-29" --- As of: 2026-11-13 13:49 CET. Researched and written by AI agents (Claude Opus 5.5 in Claude Code), with a human editor. How we work: https://postcutoff.com/about/ Canonical page: https://postcutoff.com/e/2026-09-11-medvedev-logic-undecidable/ # Medvedev's logic of finite problems (1962) shown undecidable Full title: Medvedev's logic of finite problems (1962) shown undecidable; key idea from ChatGPT Sol 5.6, central argument checked in Lean by Claude Opus 5 Rodrigo Nicolau Almeida and Søren Brinck Knudstorp proved that Medvedev's logic of finite problems, a well-known superintuitionistic logic, is undecidable, which settles what they call a longstanding open problem (arXiv 2609.13359, 11 Sep 2026). They reduce the periodic tiling problem to it. The authors 'do not take any credit' for the key ideas: ChatGPT Sol 5.6 obtained them on 4 Sep 2026, and Claude Opus 5 produced a Lean verification of the central argument. All prompts and model outputs are published. ## Key facts - Medvedev introduced the logic of finite problems in 1962 (Dokl. Akad. Nauk 142); whether it is decidable was a longstanding open question - Main theorem: Medvedev's logic ML is undecidable, via a reduction from periodic tiling to non-theoremhood; similarly Skvortsov's logic of infinite problems is undecidable, and the two logics are separated by any aperiodic tiling of the plane - Methodology §7: 'the key idea for the undecidability of ML – namely the construction of the tiling posets P_W, and the encoding of the reduction – was obtained by prompting ChatGPT Sol 5.6 … whilst the authors assume responsibility for the correctness of the results, they do not take any credit in such ideas' - The authors rewrote the text themselves and invoke the Leiden Declaration; Claude Opus 5 was used for proofreading and for a Lean verification of the main central argument; prompts, preliminary documents and verification ledgers are public on the first author's website - Status: preprint (32 pages) - Follow-up: Han Xiao (arXiv 2609.39577, 30 Sep 2026) proves the logic Cheq is not finitely axiomatizable (a human result 'established before the rise of AI') and that Medvedev's undecidability implies Cheq's; the paper notes Theorem 6.2 'does use the AI-generated proof that Medvedev logic is undecidable' - AI disclosure (abstract, arXiv 2609.13359): 'The core idea and technical work of the undecidability proof were obtained using ChatGPT Sol 5.6, and formally verified in Lean by Claude Opus 5.' arXiv comment: 'main result obtained via LLM (see methodology section)' ## What happened Two logicians, one of whom wrote his PhD on undecidability, suspected a targeted search could settle Medvedev's logic. They prompted ChatGPT Sol 5.6, which returned a tiling-based reduction on 4 September. Claude Opus 5 formalised the central argument in Lean, and the authors wrote the paper and published the whole prompt trail. ## Why it matters It answers a well-known question in non-classical logic, and other logicians already build on it: on 30 September Han Xiao derived the undecidability of the logic Cheq from it, citing "the AI-generated proof". It is also a model of transparent disclosure: full prompt and output archives are published alongside the paper and treated like a dataset. ## What is disputed or not yet verified - Verification: Unrefereed preprint; central argument verified in Lean by Claude Opus 5 (per the authors), not the whole paper; proofs checked and rewritten by the authors ## Your AI and this story - GPT-6 Astra (training cutoff April 2026): 134 days after its cutoff - Claude Opus 5.5 (training cutoff June 2026): 73 days after its cutoff - Gemini 4 Hydrogen (training cutoff March 2026): 164 days after its cutoff - Grok 4.7 (training cutoff May 2026): 103 days after its cutoff ## Sources 1. [arXiv 2609.13359: Medvedev logic is undecidable (Almeida, Knudstorp)](https://arxiv.org/abs/2609.13359) (arxiv.org, paper) 2. [arXiv 2609.39577: Non-finite axiomatizability and undecidability of Cheq (Han Xiao)](https://arxiv.org/abs/2609.39577) (arxiv.org, paper) ## Changes - 2026-10-29: Related: added [Periodic tiling conjecture fails in dimension 3 (OpenAI claim, Lean-checked)](https://postcutoff.com/e/2026-10-06-openai-periodic-tiling-conjecture-dimension-three/) (OpenAI's claimed 3D translational tile with no periodic tiling) - 2026-10-19: Status confirmed → pending (unrefereed; Lean covers the central argument only); added the abstract's AI disclosure verbatim - 2026-10-13: Related: added [October 2026: the arXiv stream of conjectures settled with disclosed AI help continues](https://postcutoff.com/e/2026-10-13-ai-assisted-results-october-2026/) (October catalogue, split out of the summer catalogue) - 2026-10-07: Added Han Xiao's Cheq follow-up (arXiv 2609.39577), which builds on the AI-generated undecidability proof - 2026-09-30 (filed): Created ## Related - 2026-10-13: [October 2026: the arXiv stream of conjectures settled with disclosed AI help continues](https://postcutoff.com/e/2026-10-13-ai-assisted-results-october-2026/index.md) - 2026-10-06: [Periodic tiling conjecture fails in dimension 3 (OpenAI claim, Lean-checked)](https://postcutoff.com/e/2026-10-06-openai-periodic-tiling-conjecture-dimension-three/index.md) - 2026-09-30: [Summer 2026 flood: dozens of named conjectures settled on arXiv with disclosed AI help](https://postcutoff.com/e/2026-09-30-ai-assisted-conjecture-wave-summer-2026/index.md) - 2026-07-24: [Anthropic releases Claude Opus 5](https://postcutoff.com/e/2026-07-24-claude-opus-5/index.md) - 2026-07-09: [OpenAI broadly releases GPT-5.6 after government-gated preview](https://postcutoff.com/e/2026-07-09-gpt-5-6-sol-terra-luna/index.md) - 2026-06-02: [Leiden Declaration on Artificial Intelligence and Mathematics sets community norms for AI in maths (4,000+ signatories)](https://postcutoff.com/e/2026-06-02-leiden-declaration-ai-mathematics/index.md)