Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913021909008384 |
|---|---|
| author | Huseynzade, Rafig |
| author_facet | Huseynzade, Rafig |
| contents | We introduce Psi-Turing Machines (Psi-TM): classical Turing machines equipped with a constant-depth introspection interface $ ι$ and an explicit per-step information budget $ B(d,n)=c\,d\log_2 n $. With the interface frozen, we develop an information-theoretic lower-bound toolkit: Budget counting, $ Ψ$-Fooling, and $ Ψ$-Fano, with worked examples $ L_k $ and $ L_k^{\mathrm{phase}} $. We prove an oracle-relative separation $ P^Ψ \neq NP^Ψ $ and a strict depth hierarchy, reinforced by an Anti-Simulation Hook that rules out polynomial emulation of $ ι_k $ using many calls to $ ι_{k-1} $ under the budget regime. We also present two independent platforms (Psi-decision trees and interface-constrained circuits IC-AC$^{0}$/IC-NC$^{1}$) and bridges that transfer bounds among machine, tree, and circuit with explicit poly/log losses. The model preserves classical computational power outside $ ι$ yet enables precise oracle-aware statements about barriers (relativization; partial/conditional progress on natural proofs and proof complexity). The aim is a standardized minimal introspection interface with clearly accounted information budgets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_08577 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations Huseynzade, Rafig Computational Complexity Formal Languages and Automata Theory Logic in Computer Science 68Q15 (Primary) 68Q05, 68Q17, 03D15 (Secondary) F.1.3; F.1.1; F.4.1 We introduce Psi-Turing Machines (Psi-TM): classical Turing machines equipped with a constant-depth introspection interface $ ι$ and an explicit per-step information budget $ B(d,n)=c\,d\log_2 n $. With the interface frozen, we develop an information-theoretic lower-bound toolkit: Budget counting, $ Ψ$-Fooling, and $ Ψ$-Fano, with worked examples $ L_k $ and $ L_k^{\mathrm{phase}} $. We prove an oracle-relative separation $ P^Ψ \neq NP^Ψ $ and a strict depth hierarchy, reinforced by an Anti-Simulation Hook that rules out polynomial emulation of $ ι_k $ using many calls to $ ι_{k-1} $ under the budget regime. We also present two independent platforms (Psi-decision trees and interface-constrained circuits IC-AC$^{0}$/IC-NC$^{1}$) and bridges that transfer bounds among machine, tree, and circuit with explicit poly/log losses. The model preserves classical computational power outside $ ι$ yet enables precise oracle-aware statements about barriers (relativization; partial/conditional progress on natural proofs and proof complexity). The aim is a standardized minimal introspection interface with clearly accounted information budgets. |
| title | Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations |
| topic | Computational Complexity Formal Languages and Automata Theory Logic in Computer Science 68Q15 (Primary) 68Q05, 68Q17, 03D15 (Secondary) F.1.3; F.1.1; F.4.1 |
| url | https://arxiv.org/abs/2510.08577 |