Computational processes, observers and Turing incompleteness

DOI10.1016/J.TCS.2010.09.004zbMATH Open1207.68143OpenAlexW1969849830MaRDI QIDQ616506FDOQ616506

Authors: K. 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

Recommendations

• Computational processes and incompleteness
• The physical Church-Turing thesis: modest or bold?
• Physical computation. A mechanistic account
• Observability of Turing machines: a refinement of the theory of computation
• scientific article; zbMATH DE number 1405574

zbMATH Keywords

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

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Recursively (computably) enumerable sets and degrees (03D25) Undecidability and degrees of sets of sentences (03D35)

Cites Work

• Title not available (Why is that?)
• Universality in elementary cellular automata
• Title not available (Why is that?)
• Languages, equicontinuity and attractors in cellular automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• The recursively enumerable degrees are dense
• Title not available (Why is that?)
• On Computable Numbers, with an Application to the Entscheidungsproblem
• ∏ 0 1 Classes and Degrees of Theories
• Title not available (Why is that?)
• Classical recursion theory. Vol. II
• β-Recursion Theory
• Computation theory of cellular automata
• Digital mechanics. An information process based on reversible universal cellular automata
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Recursively enumerable sets of positive integers and their decision problems
• Random sequence generation by cellular automata
• On the degrees less than 0'
• Title not available (Why is that?)
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• Title not available (Why is that?)
• The upper semi-lattice of degrees of recursive unsolvability
• ∑ n Definable Sets without ∑ n Induction
• Cellular automata and intermediate degrees.
• Classifying circular cellular automata
• The undecidability of the recursively enumerable degrees
• Negative solutions to Post's problem. II
• The Kleene Symposium. Proceedings of the Symposium held June 18-24, 1978 at Madison, Wisconsin, U.S.A
• Post's problem without admissibility
• Post's problem for supertasks has both positive and negative solutions
• An explicit solution to Post's problem over the reals
• Cambridge summer school in mathematical logic, held in Cambridge/England, August 1-21, 1971
• Degrees of unsolvability associated with classes of formalized theories
• Title not available (Why is that?)
• Model checking one-dimensional cellular automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Computability Theory and Differential Geometry
• Embeddings of \(N_5\) and the contiguous degrees
• Transition phenomena in cellular automata rule space

Cited In (2)

• Computational processes and incompleteness
• Physical Systems as Constructive Logics

Uses Software

• WoLFram

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q616506)