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

fi:7656 - Fundamenta Informaticae, March 7, 2023, Volume 188, Issue 2
On Completeness of Cost Metrics and Meta-Search Algorithms in $-Calculus

Authors: Eugene Eberbach

    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.

    Volume: Volume 188, Issue 2
    Published on: March 7, 2023
    Accepted on: February 27, 2023
    Submitted on: July 7, 2021
    Keywords: Computer Science - Computational Complexity,Computer Science - Logic in Computer Science


    Consultation statistics

    This page has been seen 15 times.
    This article's PDF has been downloaded 7 times.