Theoretical computer science: computability, decidability and logic

DOI10.1007/978-3-030-06170-8_1zbMATH Open1547.68198MaRDI QIDQ6602262

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

Publication date: 11 September 2024

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)

Cites Work

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

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