The Applicability of $-Calculus to Solve Some Turing Machine Undecidable Problems

Abstract

The $-calculus process algebra for problem solving applies the cost performance measures to converge in finite
time or in the limit to optimal solutions with minimal problem solving costs. The $-calculus belongs to superTuring
models of computation. Its main goal is to provide the support to solve hard computational problems. It allows also
to solve in the limit some undecidable problems. In the paper we demonstrate how to solve in the limit Turing Machine
Halting Problem, to approximate the universal search algorithm, to decide diagonalization language, nontrivial
properties of recursively enumerable languages, and how to solve Post Correspondence Problem and Busy Beaver
Problem.