Theoretical computer science: computability, decidability and logic

DOI10.1007/978-3-030-06170-8_1MaRDI QIDQ6602262zbMATH OpenFDO

Authors Olivier Bournez, Gilles Dowek, Rémi Gilleron, Serge Grigorieff, Jean-Yves Marion, Simon Perdrix, Sophie Tison

Publication date 11 September 2024

Full work available at URL https://doi.org/10.1007/978-3-030-06170-8_1

Mathematics Subject Classification ID

Turing machines and related notions (03D10) General topics in the theory of computing (68Q01) Classical models of computation (Turing machines, etc.) (68Q04)

Recommendations

• What machines can and cannot do
• scientific article; zbMATH DE number 42807
• Mathematical and technological computability
• Computability theory
• scientific article; zbMATH DE number 194513

Cites work

• A Natural Axiomatization of Computability and Proof of Church's Thesis
• A survey on continuous time computations
• About primitive recursive algorithms
• Abstract state machines capture parallel algorithms
• Abstract state machines capture parallel algorithms: correction and extension
• An Algorithm for the General Petri Net Reachability Problem
• An Informal Arithmetical Approach to Computability and Computation
• An Unsolvable Problem of Elementary Number Theory
• Analog computation with dynamical systems
• Analog computers and recursive functions over the reals.
• Automata, Languages and Programming
• Beweistheoretische Erfassung der unendlichen Induktion in der Zahlentheorie
• Classical physics and the Church--Turing Thesis
• Classical recursion theory. The theory of functions and sets of natural numbers
• Combinatorial foundations of information theory and the calculus of probabilities
• Computational complexity with experiments as oracles
• Computing minimum with primitive recursion over lists
• Decidability of a portion of the predicate calculus
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Definability and decision problems in arithmetic
• Embedding Pure Type Systems in the Lambda-Pi-Calculus Modulo
• Fault tolerant solutions to the firing squad synchronization problem in linear cellular automata
• Fields of logic and computation. Essays dedicated to Yuri Gurevich on the occasion of his 70th birthday
• From Turing machines to computer viruses
• General recursive functions of natural numbers.
• Generating the greatest common divisor, and limitations of primitive recursive algorithms
• Hilbert's Programs: 1917–1922
• scientific article; zbMATH DE number 1687041 (Why is no real title available?)
• scientific article; zbMATH DE number 1722668 (Why is no real title available?)
• scientific article; zbMATH DE number 5999715 (Why is no real title available?)
• scientific article; zbMATH DE number 3112803 (Why is no real title available?)
• scientific article; zbMATH DE number 3131080 (Why is no real title available?)
• scientific article; zbMATH DE number 5605129 (Why is no real title available?)
• scientific article; zbMATH DE number 4147469 (Why is no real title available?)
• scientific article; zbMATH DE number 3664359 (Why is no real title available?)
• scientific article; zbMATH DE number 3728250 (Why is no real title available?)
• scientific article; zbMATH DE number 15889 (Why is no real title available?)
• scientific article; zbMATH DE number 42059 (Why is no real title available?)
• scientific article; zbMATH DE number 3586989 (Why is no real title available?)
• scientific article; zbMATH DE number 1324438 (Why is no real title available?)
• scientific article; zbMATH DE number 1339873 (Why is no real title available?)
• scientific article; zbMATH DE number 512790 (Why is no real title available?)
• scientific article; zbMATH DE number 727991 (Why is no real title available?)
• scientific article; zbMATH DE number 1951198 (Why is no real title available?)
• scientific article; zbMATH DE number 1993590 (Why is no real title available?)
• scientific article; zbMATH DE number 1543040 (Why is no real title available?)
• scientific article; zbMATH DE number 3993540 (Why is no real title available?)
• scientific article; zbMATH DE number 1909830 (Why is no real title available?)
• scientific article; zbMATH DE number 2123258 (Why is no real title available?)
• scientific article; zbMATH DE number 783760 (Why is no real title available?)
• scientific article; zbMATH DE number 3222098 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• scientific article; zbMATH DE number 3338162 (Why is no real title available?)
• scientific article; zbMATH DE number 3349775 (Why is no real title available?)
• Intensional interpretations of functionals of finite type I
• La théorie des fonctions récursives et ses applications. (Exposé d'information générale)
• Linear logic
• Mathematical Theory of the Differential Analyzer
• On a problem of formal logic.
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On Computable Numbers, with an Application to the Entscheidungsproblem
• On computable sequences
• On non-computable functions
• On primitive recursive algorithms and the greatest common divisor function
• On the computational power of neural nets
• On the definition of an algorithm
• On the definitions of computable real continuous functions
• Philosophie der Mathematik und Naturwissenschaft. I, II.
• Polynomial differential equations compute all real computable functions on computable compact intervals
• Proof normalization modulo
• Random-Access Stored-Program Machines, an Approach to Programming Languages
• Recursive Predicates and Quantifiers
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Sequential abstract-state machines capture sequential algorithms
• Small deterministic Turing machines
• Solvability of the halting problem for certain classes of Turing machines
• Some recent developments on Shannon's General Purpose Analog Computer
• Step by Recursive Step: Church's Analysis of Effective Calculability
• Storage Modification Machines
• Stratification and cut-elimination
• Strong planning under uncertainty in domains with numerous but identical elements (a generic approach)
• Sur les ensembles définissables de nombres réels. I.
• Surprising areas in the quest for small universal devices
• Synchronization of a bounded degree graph of cellular automata with nonuniform delays in time \(D\lfloor \log_mD\rfloor\)
• Synthesis of ML programs in the system Coq
• System \(T\), call-by-value and the minimum problem
• Systems of logic based on ordinals.
• The calculus of constructions
• The Church-Turing Thesis over Arbitrary Domains
• The consistency of arithmetics
• The decision problem for standard classes
• The definition of random sequences
• The differential analyzer. A new machine for solving differential equations.
• The domino problem of the hyperbolic plane is undecidable
• The duality of computation
• The limits of empiricism.
• The many forms of hypercomputation
• THE PROBLEM OF SOLVABILITY OF EQUATIONS IN A FREE SEMIGROUP
• The synchronization of nonuniform networks of finite automata
• The undecidability of the domino problem
• Theory and Applications of Models of Computation
• Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
• Time bounded random access machines
• Universal diophantine equation
• Untersuchungen über das logische Schließen. II.
• Weak Second‐Order Arithmetic and Finite Automata
• Zum Hilbertschen Aufbau der reellen Zahlen.
• ÜBER EINE BISHER NOCH NICHT BENÜTZTE ERWEITERUNG DES FINITEN STANDPUNKTES
• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I.

This page was built for publication: Theoretical computer science: computability, decidability and logic

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