On Completeness of Cost Metrics and Meta-Search Algorithms in $-Calculus

DOI10.3233/FI-222142MaRDI QIDQ6040672zbMATH OpenOpenAlexFDO

Authors Eugene Eberbach

Publication date 19 May 2023

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.15969

zbMATH Keywords

\$-calculusa-decidabilityautomatic problem solvingautomatic programmingcost metrics completenessD-completenesse-decidabilityH-completenessi-decidabilityintractablitymeta-search algorithms completenessnon-recursively enumerable algorithmsp-decidabilityrecursive algorithmsrecursively enumerable but not recursive algorithmsreduction techniquessuper-recursive algorithmssuper-Turing computationU-completenessundecidability

Mathematics Subject Classification ID

Computer science (68-XX)

Abstract: In the paper we define three new complexity classes for Turing Machine undecidable problems inspired by the famous Cook/Levin's NP-complete complexity class for intractable problems. These are U-complete (Universal complete), D-complete (Diagonalization complete) and H-complete (Hypercomputation complete) classes. In the paper, in the spirit of Cook/Levin/Karp, we started the population process of these new classes assigning several undecidable problems to them. We justify that some super-Turing models of computation, i.e., models going beyond Turing machines, are tremendously expressive and they allow to accept arbitrary languages over a given alphabet including those undecidable ones. We prove also that one of such super-Turing models of computation - the $-Calculus,designedasatoolforautomaticproblemsolvingandautomaticprogramming,hasalsosuchtremendousexpressiveness.Weinvestigatealsocompletenessofcostmetricsandmeta-searchalgorithmsin$-calculus.

Recommendations

• On meta complexity of propositional formulas and propositional proofs
• scientific article; zbMATH DE number 2080295
• scientific article; zbMATH DE number 7515768
• Methods for algorithmic meta theorems
• Algorithmic meta-theorems
• Algorithmic Meta-theorems
• On Search Problems in Complexity Theory and in Logic (Abstract)
• Completeness and admissibility for general heuristic search algorithms -- a theoretical study: Basic concepts and proofs

Cites work

• \$-calculus of bounded rational agents: flexible optimization as search under bounded resources in interactive systems
• A variant of a recursively unsolvable problem
• Alan Turing: Life and Legacy of a Great Thinker
• Approximate reasoning in the algebra of bounded rational agents
• scientific article; zbMATH DE number 5604101 (Why is no real title available?)
• scientific article; zbMATH DE number 1296290 (Why is no real title available?)
• scientific article; zbMATH DE number 1033559 (Why is no real title available?)
• Hypercomputation
• On Computable Numbers, with an Application to the Entscheidungsproblem
• On hypercomputation, universal and diagonalization complete problems
• On non-computable functions
• Super-Recursive Algorithms
• The \$-calculus process algebra for problem solving: A paradigmatic shift in handling hard computational problems

Cited in

(1)

• scientific article; zbMATH DE number 7515768 (Why is no real title available?)

This page was built for publication: On Completeness of Cost Metrics and Meta-Search Algorithms in $-Calculus

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