2021/01/22 by Stephen Wolfram, Wolfram, Stephen
Computer Science · #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.2101.10907
openalex publication_date 2021/01/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
As an example of the concept of rulial space, we explore the case of simple Turing machines. We construct the rulial multiway graph which represents the behavior of all possible Turing machines with a certain class of rules. This graph (which is a Cayley graph of a "Turing machine group") gives a map of the space of non-deterministic Turing machines. We investigate the subgraph formed by deterministic machines, and explore the relationship to the P vs. NP problem. We also consider the implications of features of rulial space for physics, including estimating the maximum speed \rho in rulial space, relations between rulial black holes and computational reducibility, and interpretations of hypercomputation.