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

arXiv: https://arxiv.org/abs/2106.15969 · HTML: https://mlsanity.com/paper/2106.15969/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2021.

## Built on by (most cited first, 2 of 2)

- [Evolutionary Automata and Deep Evolutionary Computation](https://mlsanity.com/paper/2411.15008/) (2024)
- [Turing or Cantor: That is the Question](https://mlsanity.com/paper/2604.10418/) (2026)

## Abstract (arXiv)

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.