Open Source
Beyond the Turing threshold: Productive grammars generate essentially undecidable languages
arXiv cs.CR0 views
arXiv:2609.11385v2 Announce Type: replace-cross Abstract: Emil Post's productive sets are not even semi-computable, let alone computable, being thus essentially incomputable. Accordingly, formal languages whose set of words is a (completely) productive set are essentially undecidable. In this article, I elaborate on Post productivity from the viewpoint of formal language theory: I design formal grammars that emulate the construction of productive sets of natural numbers and are thus beyond Turing-decidability.
Source：https://arxiv.org/abs/2609.11385PreviousMarkTune: Improving the Quality-Detectability Trade-off in Model-Embedded LLM WatermarkingNextRetryBench: Separating Retry Permission from Recovery Outcomes in GPT Tool Use
Related posts
Open Source Didn't Ban AI Code. 83% of Its AI Policies Allow It, With One Catch
0dev.to Git
Orbit: A High-Performance Terminal Workspace & System Monitor in Rust with WASM Plugins
0dev.to Rust
Forecasting the U.S. Senate with Prediction Markets and Monte Carlo Simulations
0dev.to AI
VoiceStudio: open-source, fully-local ElevenLabs alternative
0Hacker News New
Show HN: X Mode – macOS-style window management for Omarchy
0Hacker News Show
Show HN: Orca Style Workspaces for Herdr
0Hacker News Show