Back to Search
Start Over
On Completeness of Cost Metrics and Meta-Search Algorithms in $-Calculus.
- Source :
- Fundamenta Informaticae; 2022, Vol. 188 Issue 2, p63-90, 28p
- Publication Year :
- 2022
-
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, designed as a tool for automatic problem solving and automatic programming, has also such tremendous expressiveness. We investigate also completeness of cost metrics and meta-search algorithms in $-calculus. [ABSTRACT FROM AUTHOR]
- Subjects :
- TURING machines
ALGORITHMS
PROBLEM solving
COST
METAHEURISTIC algorithms
Subjects
Details
- Language :
- English
- ISSN :
- 01692968
- Volume :
- 188
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- Fundamenta Informaticae
- Publication Type :
- Academic Journal
- Accession number :
- 162504782
- Full Text :
- https://doi.org/10.3233/FI-222142