2025/08/29 by Rafig Huseynzade, Huseynzade, Rafig · 1 voice
Computer Science · #03D15 (Secondary) #68Q15 (Primary) 68Q05 #68Q17 #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #F.1.1 #F.1.3 #F.4.1 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.2510.08577
openalex publication_date 2025/08/29 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28
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 dlog2 n . With the interface frozen, we develop an information-theoretic lower-bound toolkit: Budget counting, Ψ-Fooling, and Ψ-Fano, with worked examples Lk and Lkphase . We prove an oracle-relative separation PΨ ≠ 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-AC0/IC-NC1) 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.