Impossibility of an algorithm for the decision problem in finite classes

DOI10.1090/trans2/023/01zbMath0121.01507OpenAlexW4244028915MaRDI QIDQ5731786

B. A. Trakhtenbrot

Publication date: 1963

Published in: Nine Papers on Logic and Quantum Electrodynamics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/trans2/023/01

zbMATH Keywords

mathematical logic

Related Items

Expressive Completeness of Separation Logic with Two Variables and No Separating Conjunction, Succinct definitions in the first order theory of graphs, Nonconvergence, undecidability, and intractability in asymptotic problems, Separation logics and modalities: a survey, Trakhtenbrot theorem and first-order axiomatic extensions of MTL, On the almighty wand, Computational complexity of theories of a binary predicate with a small number of variables, The decision problem for database dependencies, LTL over integer periodicity constraints, LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE