A New General Approach to the Theory of the Many‐One Equivalence of Decision Problems for Algorithmic Systems

DOI10.1002/malq.19790250707zbMath0429.03016OpenAlexW2028126029MaRDI QIDQ3866085

Egon Börger

Publication date: 1979

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19790250707

zbMATH Keywords

decision problemsTuring machinerepresentation theoremssemi-Thue systemregister machinepartial recursive functionsalgorithmic systemsMarkov algorithmrecursive reductionmany-one equivalencepartial implicational propositional calculus in two variablesPost normal calculusrecursive classes of first-order logical formulae with equalityword problem of Thue systems

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Word problems, etc. in computability and recursion theory (03D40) Other degrees and reducibilities in computability and recursion theory (03D30) Turing machines and related notions (03D10) Thue and Post systems, etc. (03D03)

Related Items (2)

The reachability problem for Petri nets and decision problems for Skolem arithmetic ⋮ Degree problems for modular machines

This page was built for publication: A New General Approach to the Theory of the Many‐One Equivalence of Decision Problems for Algorithmic Systems