Computational processes, observers and Turing incompleteness

DOI10.1016/j.tcs.2010.09.004zbMath1207.68143OpenAlexW1969849830MaRDI QIDQ616506

Klaus Sutner

Publication date: 10 January 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.09.004

zbMATH Keywords

cellular automatondiscrete dynamical systemcomputational processdegrees of unsolvabilityintermediate degreesWolfram's notion of computational processes

Mathematics Subject Classification ID

Uses Software

• WoLFram

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Transition phenomena in cellular automata rule space
• Classifying circular cellular automata
• Computation theory of cellular automata
• Random sequence generation by cellular automata
• The Kleene Symposium. Proceedings of the Symposium held June 18-24, 1978 at Madison, Wisconsin, U.S.A
• Post's problem without admissibility
• Negative solutions to Post's problem. II
• Classical recursion theory. Vol. II
• Cellular automata and intermediate degrees.
• Post's problem for supertasks has both positive and negative solutions
• An explicit solution to Post's problem over the reals
• The recursively enumerable degrees are dense
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Cambridge summer school in mathematical logic, held in Cambridge/England, August 1-21, 1971
• On the degrees less than 0'
• Digital mechanics. An information process based on reversible universal cellular automata
• The upper semi-lattice of degrees of recursive unsolvability
• Degrees of unsolvability associated with classes of formalized theories
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• The undecidability of the recursively enumerable degrees
• β-Recursion Theory
• ∑ n Definable Sets without ∑ n Induction
• Languages, equicontinuity and attractors in cellular automata
• FINITELY PRESENTED GROUP WHOSE WORD PROBLEM HAS THE SAME DEGREE AS THAT OF AN ARBITRARILY GIVEN THUE SYSTEM (AN APPLICATION OF METHODS OF BRITTON)
• The Friedberg-Muchnik Theorem Re-Examined
• ∏ 0 1 Classes and Degrees of Theories
• Computability Theory and Differential Geometry
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Recursively enumerable sets of positive integers and their decision problems
• Embeddings of \(N_5\) and the contiguous degrees

This page was built for publication: Computational processes, observers and Turing incompleteness