This is arXiv:1412.1044 version 20160902, and it is licensed as cc-by. Any
comments on it to<EMAIL_ADDRESS>are welcome.

Problem Theory

Ramón Casares

orcid: 0000-0003-4973-3128

The Turing machine, as it was presented by Turing himself, models the
calculations done by a person. This means that we can compute whatever any
Turing machine can compute, and therefore we are Turing complete. The question
addressed here is why, Why are we Turing complete? Being Turing complete also
means that somehow our brain implements the function that a universal Turing
machine implements. The point is that evolution achieved Turing completeness,
and then the explanation should be evolutionary, but our explanation is
mathematical. The trick is to introduce a mathematical theory of problems,
under the basic assumption that solving more problems provides more survival
opportunities. So we build a problem theory by fusing set and computing
theories. Then we construct a series of resolvers, where each resolver is
defined by its computing capacity, that exhibits the following property: all
problems solved by a resolver are also solved by the next resolver in the
series if certain condition is satisfied. The last of the conditions is to be
Turing complete. This series defines a resolvers hierarchy that could be seen
as a framework for the evolution of cognition. Then the answer to our question
would be: to solve most problems. By the way, the problem theory defines
adaptation, perception, and learning, and it shows that there are just three
ways to resolve any problem: routine, trial, and analogy. And, most
importantly, this theory demonstrates how problems can be used to found
mathematics and computing on biology.

Keywords: problem solving; adaptation, perception & learning; Turing
completeness; resolvers hierarchy; evolution of cognition.

Problem Theory

§1 Introduction. 3

§1.1 Object. 3

§1.2 Contents. 4

§2 Theory. 5

§2.1 Problem. 5

§2.2 Solution. 6

§2.3 Resolution. 6

§2.4 Eight Concepts. 7

§3 Sets. 7

§3.1 Problems. 7

§3.2 Solutions. 9

§3.3 Routines and Trials. 11

§3.4 Analogies. 12

§3.5 Metaproblems. 14

§3.6 Resolution Typology. 16

§4 Computers. 17

§4.1 Turing Machine. 17

§4.2 Turing Completeness. 19

§4.3 Turing’s Thesis. 22

§4.4 Full Resolution Machine. 24

§4.5 Problem Topology. 27

§5 Resolvers. 29

§5.1 Semantics and Syntax. 29

§5.2 Mechanism. 31

§5.3 Adapter. 32

§5.4 Perceiver. 34

§5.5 Learner. 36

§5.6 Subject. 38

§5.7 Resolvers Hierarchy. 39

§6 Conclusion. 41

§6.1 Purpose. 41

§6.2 Countability. 42

§6.3 Intuition. 43

References. 44

§1 Introduction

Devoid of problems, thinking is useless.

Warning This paper does not explain how to solve, nor how to resolve, any
problem.

§1.1 Object

The object of this paper is to present a mathematical theory of problems. The
resulting problem theory provides meaning to set theory and to computing
theory.

Problems are nearly everywhere. We can say that mathematics is all about
mathematical problems, but also that physics is all about physical problems,
and philosophy is all about philosophical problems. I said nearly because
there are not problems in a river; a river just flows. So, where are problems?

This problem theory gives an answer: There are problems where there is
freedom. Determinists will surely object, but they should note that if there
were only uncertainty, and not the possibility of doing otherwise, then
problem resolving would be purposeless and absurd. Nevertheless, in this
theory freedom cannot exist by itself, but freedom is always limited by a
condition and both together, freedom and a condition, are a problem. In fact,
the resolution of any problem is the process of spending all of its freedom
while still satisfying the condition. So resolving is fighting freedom away.
And, if people fight for freedom, it is because we want problems; in fact, not
having any problem is boring. But I would say more, we are devices exquisitely
selected to resolve problems, because surviving is literally the problem of
being dead or alive: “To be, or not to be—that is the question.”

I am digressing, sorry! The point is that problems are related to sets at the
very bottom: for each problem there is a condition that determines if anything
is a solution to it or not, so for each problem there is a set, the set of its
solutions, and the condition is its characteristic function. This means that
problems and sets are just two names for the same thing. So problem theory,
being just a rewording of set theory, would be a better foundation for
mathematics than set theory, because problems are more related to thinking
than sets are.

We have just seen how problems and solutions fit with sets, but we have seen
nothing about resolutions, that is, the ways to go from a problem to its
solutions. It is a fact that computing is helping us in resolving many
problems. Perhaps too many: How our modern society would subsist without
computers? I am digressing again, sorry! The right question is: What is the
relation between problem resolving and computing?

Computing is the mechanical manipulation of strings of symbols. Mechanical in
the sense that the manipulations do not take into account the meaning of the
symbols, but they just obey blindly a finite set of well-defined rules. Being
meaningless, what could be the purpose of computing? Historically, computing
resulted from two apparently different pursuits: the foundation of
mathematics, and the enhancement of calculating machines. The second, the
development of mechanical aids to calculation, is easier to understand. When
we learn the algorithm for division we readily appreciate that those fixed
rules can be better applied by a machine than by a person. This explains why
an arithmetic calculator comes handy when resolving a problem that requires
performing a numerical division. And it could also help us to understand why
computation was seen as the ideal for mathematical rigor, and then how
computing relates to the foundations of mathematics.

But, again, what is the purpose of mathematical formalization? Is it true that
a complete formalization of mathematics would render it meaningless? What
would be the use of something meaningless? And again, the arithmetic
calculator, dividing for us, answers the three questions: formalization
prevents mistakes and assures that nothing has been taken for granted, and,
while it is literally meaningless, it is not useless if the formalism helps us
in resolving problems. Though pending on an if, formalism is not yet lost.
This paper cuts that Gordian knot by showing that problem resolving is
computing.

In fact, that ‘resolving is computing’ comes from the founding paper of
computing. Turing (1936) proved that the Entscheidungsproblem, which is the
German word for ‘decision problem’, is unsolvable, because it cannot be solved
by any Turing machine. For this proof to be valid, ‘solved by a Turing
machine’ has to be equal to ‘solved’, and therefore ‘resolved by computing’
has to be redundant.

Summarizing, a problem is a set, and resolving is computing. This is how this
problem theory relates to set and computing theories at the highest level of
abstraction. For a more detailed view you should continue reading this paper.

§1.2 Contents

The object of this paper is to introduce a mathematical theory of problems.
Because our approach is minimalist, aiming to keep only what is essential, we
will define a problem theory from first principles. Section §2 contains this
problem theory, including its eight concepts: problem, with freedom and
condition; resolution, with routine, trial and analogy; and solution. Some
care is advisable to distinguish ‘solution’ from ‘resolution’, because while
they are usually considered synonyms, they are very distinct concepts in this
theory: a solution is a state, and a resolution is a transition. Then that ‘a
problem is resolved unsolvable’ achieves a very precise meaning.

Section §3 translates the problem theory to set theory. Subsection §3.1
defines what a problem is, and what is the set of its solutions is defined in
Subsection §3.2. Then, in Subsection §3.3, we develop the first two ways to
resolve a problem, by routine and by trial, while we devote Subsection §3.4 to
the third way, by analogy. The conclusion of these two subsections is that
there is a general form that includes the three forms. Then we observe that
looking for a resolution to a problem is also a problem, the metaproblem, so
Subsection §3.5 deals with metaproblems. The last subsection of this section,
Subsection §3.6, shows that there is only one level of problem meta-ness and
that there are five types of resolution.

The next section, Section §4, is about computing. In Subsection §4.1 we
present the Turing machine, concluding that all computing is inside countable
sets. In Subsection §4.2 we deal with universal computers and Turing
completeness. Then, in Subsection §4.3, we explain that Turing’s thesis
implies that everything is an expression, that resolving is computing, and
that all problem sets are countable. In Subsection §4.4, we introduce the full
resolution machine, and we show some equivalences between problem theory and
computing theory. In the last subsection of this section, Subsection §4.5, we
show that there are five types of problem.

Section §5 is about resolvers, that is, devices that resolve problems. In the
first subsection, §5.1, we present the practical scenario, where functions are
not solutions, so we distinguish the semantics of solutions from the syntax of
functions, and we define the range of a resolver as the set of problems that
the resolver solves, and the power of a resolver as the set of problems that
the resolver resolves. Then we construct a series of five resolvers:

$\circ$ Mechanism, Subsection §5.2, is any device that implements a semantic
unconditional computation. We show that mechanisms can resolve problems by
routine.

$\circ$ Adapter, in §5.3, is any device that implements a semantic conditional
computation. We show that adapters can resolve problems by trial.

$\circ$ Perceiver, in §5.4, is any device that implements a semantic
functional computation or a syntactic unconditional computation. We show that
perceivers can resolve problems by analogy and metaproblems by routine.

$\circ$ Learner, in §5.5, is any device that implements a syntactic
conditional computation. We show that learners can resolve metaproblems by
trial.

$\circ$ Subject, in §5.6, is any device that implements a syntactic functional
computation. We show that subjects can resolve metaproblems by analogy.

In addition, we show that the range and power of each resolver in the series
includes the range and power of the previous one, provided that a specific
condition is satisfied. The last of these conditions requires the subject to
be Turing complete. So, in the last subsection of this section, §5.7, we
summarize the findings of the section: we show that there is a hierarchy of
five types of resolver, and that the problem theory is complete. The theory is
complete because Turing completeness is the maximum computing capacity, and
this means that there are exactly three ways to resolve any problem: routine,
trial, and analogy. Finally, we argue that we are the Turing complete subjects
that have resulted from an evolution of resolvers of the survival problem.

The paper finishes with some conclusions, in Section §6. In the first
subsection, §6.1, we explain how problem theory provides purpose and meaning
to set theory and to computing theory. In the next subsection, §6.2, we argue
that countableness is the golden mean that keeps paradoxes under control. And
in the last subsection, §6.3, we explore what would be the implications of
non-computable ways of resolving, as intuition.

§2 Theory

§2.1 Problem

Every problem is made up of freedom and of a condition. There have to be
possibilities and freedom to choose among them, because if there is only
necessity and fatality, then there is neither a problem nor is there a
decision to make. The different possible options could work, or not, as
solutions to the problem, so that in every problem a certain condition that
will determine if an option is valid or not as a solution to the problem must
exist.

$\hbox{\xiirm Problem}\left\\{\vbox{\hbox{Freedom}\hbox{Condition}}\right.$

§2.2 Solution

A fundamental distinction that we must make is between the solution and the
resolution of a problem. Resolving is to searching as solving is to finding,
and please note that one can search for something that does not exist.

Resolving | $\cdot$ | Searching
---|---|---
Solving | $\cdot$ | Finding

Thus, resolution is the process that attempts to reach the solutions to the
problem, while a solution of the problem is any use of freedom that satisfies
the condition. In the state-transition jargon: a problem is a state of
ignorance, a solution is a state of satisfaction, and a resolution is a
transition from uncertainty to certainty.

$\hbox{\xiirm Problem}\mathop{\hbox
to87.96683pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\hbox{\quad\xiirm
Resolution\quad}$}}\hbox{\xiirm Solution}$

We can explain this with another analogy. The problem is defined by the
tension that exists between two opposites: freedom, free from any limits, and
the condition, which is pure limit. This tension is the cause of the
resolution process. But once the condition is fulfilled and freedom is
exhausted, the solution annihilates the problem. The resolution is, then, a
process of annihilation that eliminates freedom as well as the condition of
the problem, in order to produce the solution.

$\underbrace{\vbox{ \halign{\strut\hfil\rm#\cr\xiirm Freedom\cr\xiirm
Condition\cr}}}_{\hbox{\xiirm Problem}}\,\Bigr{\\}}\mathop{\hbox
to87.96683pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\hbox{\quad\xiirm
Resolution\quad}$}}\hbox{\xiirm Solution}$

A mathematical example may also be useful in order to distinguish resolution
from solution. In a problem of arithmetical calculation, the solution is a
number and the resolution is an algorithm such as the algorithm for division,
for example.

§2.3 Resolution

There are three ways to resolve a problem: routine, trial, and analogy.

$\hbox{Resolution}\left\\{\vbox{
\hbox{Routine}\hbox{Trial}\hbox{Analogy}}\right.$

To resolve a problem by routine, that is, by knowing or without reasoning, it
is necessary to know the solutions, and it is necessary to know that they
solve that problem.

If the solutions to a problem are not known, but it is known a set of possible
solutions, then we can use a trial and error procedure, that is, we can try
the possible solutions. To resolve by trial is to test each possible solution
until the set of possible solutions is exhausted or a halting condition is
met. There are two tasks when we try: to test if a particular possibility
satisfies the problem condition, and to govern the process determining the
order of the tests and when to halt. There are several ways to govern the
process, that is, there is some freedom in governing the trial, and so, if we
also put a condition on it, for example a temporal milestone, then governing
is a problem. And there are three ways to resolve a problem (da capo).

By analogy we mean to transform a problem into a different one, called
question, which is usually composed of several subproblems. This works well if
the subproblems are easier to resolve than the original problem. There are
usually several ways to transform any problem (there is freedom), but only
those transformations that result in questions that can be resolved are valid
(which is a condition), so applying an analogy to a problem is a problem.
There are three ways to resolve the analogy, the question, and each of its
subproblems: routine, trial, and analogy (da capo). If we could translate a
problem into an analogue question, and we could find a solution to that
question, called answer, and we could perform the inverse translation on it,
then we would have found a solution to the original problem.

Problem |  | Solution
---|---|---
$\downarrow$ |  | $\uparrow$
Question | $\longrightarrow$ | Answer

§2.4 Eight Concepts

Lastly we are ready to list the eight concepts of the problem theory. They
are: problem, with freedom and condition; resolution, with routine, trial, and
analogy; and solution.

$\hbox{Problem Theory}\left\\{\vbox{ \hbox{Problem
$\left\\{\vbox{\hbox{Freedom}\hbox{Condition}}\right.$}\hbox{}\hbox{Resolution
$\left\\{\vbox{\hbox{Routine}\hbox{Trial}\hbox{Analogy}}\right.$}
\hbox{Solution}\kern 6.0pt}\right.$

§3 Sets

§3.1 Problems

§3.1.1 Notation We will refer to the set of problems as $\xiibb P$. We will
refer to the set of resolutions as $\xiibb R$. We will refer to the set of
solutions as $\xiibb S$.

Definition A resolution takes a problem and returns the set of the solutions
to the problem. Then resolutions are ${\xiibb R}={\xiibb P}\to 2^{\xiibb S}$,
where $2^{\xiibb S}$ is the powerset, or the set of the subsets, of $\xiibb
S$.

§3.1.2 Notation $\top$ stands for ‘true’, and $\bot$ for ‘false’. We will
refer to the set of these Boolean values as $\xiibb B$. ${\xiibb
B}=\\{\top,\bot\\}$.

Comment $\top=\neg\bot$ and $\bot=\neg\top$. Also $[P=\top]=P$ and
$[P=\bot]=\neg P$.

§3.1.3 Notation Given $s\in S\subseteq{\xiibb S}$ and $f\in F\subseteq({\xiibb
S}\to{\xiibb S})$, so $f:{\xiibb S}\to{\xiibb S}$ and $f(s)\in{\xiibb S}$, we
will use the following rewriting rules: $f(S)=\\{\,f(s)\mid s\in S\,\\}$,
$F(s)=\\{\,f(s)\mid f\in F\,\\}$, and $F(S)=\\{\,f(s)\mid s\\!\in\\!S\times
f\\!\in\\!F\,\\}$.

Comment As $f(s)\in{\xiibb S}$, then $f(S)\in 2^{\xiibb S}$, $F(s)\in
2^{\xiibb S}$, and $F(S)\in 2^{\xiibb S}$.

Proposition If $s\in S$ and $f\in F$, then $f(S)\subseteq F(S)$ and
$F(s)\subseteq F(S)$.

§3.1.4 Definition Problem $\pi$ is $x?P_{\pi}(x)$, where $P_{\pi}$ is any
predicate, or Boolean-valued function, on ${\xiibb S}$; so $P_{\pi}:{\xiibb
S}\to{\xiibb B}$, where $P_{\pi}(x)=\top$ means that $x$ is a solution of
$\pi$, and $P_{\pi}(x)=\bot$ means that $x$ is not a solution of $\pi$.

Comment A problem $\pi=x?P_{\pi}(x)$ is made up of freedom and of a condition,
as defined in Section §2. The condition is $P_{\pi}$, and freedom is
represented by the free variable $x$, which is free to take any value in
$\xiibb S$, $x\in{\xiibb S}$.

§3.1.5 Definition A function ${}^{*}\\!f$ is effectively calculable if there
is a purely mechanical process to find ${}^{*}\\!f(s)$ for any $s$.

Comment This definition of effective calculability was stated by Turing
(1938), §2.

Comment If the result of the calculation is finite, then an effective
calculation has to complete it. If the result of the calculation is infinite,
then an effective calculation has to proceed forever towards the result.

Notation We will refer to the set of effectively calculable functions as
${}^{*}\xiibb F$.

§3.1.6 Definition A problem $\pi$ is expressible if its condition $P_{\pi}$ is
an effectively calculable function.

Comment The result of a condition is in set ${\xiibb B}=\\{\top,\bot\\}$, so
it is always finite. Therefore a problem is not expressible if for some $x$ we
cannot calculate whether $x$ is a solution or not in a finite time.

§3.1.7 Definition The condition isomorphism is the natural isomorphism that
relates each problem $\pi$ with its condition $P_{\pi}$: for each predicate
$P$ there is a problem, $x?P(x)$, and for each problem, $\pi=x?P_{\pi}(x)$
there is a predicate, $P_{\pi}$. That is, ${\xiibb P}\Leftrightarrow({\xiibb
S}\to{\xiibb B}):x?P_{\pi}(x)\leftrightarrow P_{\pi}$.

Comment Using the condition isomorphism, two problems are equal if they have
the same condition, that is, $\pi=\rho\Leftrightarrow P_{\pi}=P_{\rho}$.

Comment The condition isomorphism abstracts freedom away.

§3.1.8 Theorem The set of problems is the set of predicates, that is, ${\xiibb
P}={\xiibb S}\to{\xiibb B}$.

Proof ${\xiibb P}\cong{\xiibb S}\to{\xiibb B}$, by the condition isomorphism,
see §3.1.7, and, abstracting freedom, ${\xiibb P}={\xiibb S}\to{\xiibb B}$.
But freedom has to be abstracted away from mathematics because freedom is free
of form and it cannot be counted nor measured. $\diamond$

Comment Although in mathematics we cannot deal with freedom, it is an
essential part of problems, see §2.1. In any case, what defines problem $\pi$
is its condition $P_{\pi}$.

§3.1.9 Lemma The name of the free variable is not important, it can be
replaced: $x?P(x)=y?P(y)$.

Proof By the condition isomorphism, and §3.1.8, both problems, $x?P(x)$ and
$y?P(y)$, are equal, $x?P(x)=y?P(y)$, because they have the same condition,
$P$. $\diamond$

Comment This means that the rule of $\alpha$-conversion stands for problem
expressions. See Curry & Feys (1958), Section 3D.

§3.1.10 Definition Let $\pi$ and $\rho$ be two problems. Then
$\pi\land\rho=x?P_{\pi}(x)\land P_{\rho}(x)$, and
$\pi\lor\rho=x?P_{\pi}(x)\lor P_{\rho}(x)$, and $\bar{\pi}=x?\neg P_{\pi}(x)$.

Comment In other words, $P_{\pi\land\rho}(x)=P_{\pi}(x)\land P_{\rho}(x)$,
$P_{\pi\lor\rho}(x)=P_{\pi}(x)\lor P_{\rho}(x)$, and $P_{\bar{\pi}}(x)=\neg
P_{\pi}(x)$.

Comment This provides a way to compose, or decompose, problems.

§3.1.11 Definition A problem $\tau$ is tautological if its condition is a
tautology; $P_{\tau}$ is a tautology, if $\forall x,\,P_{\tau}(x)=\top$. A
problem $\bar{\tau}$ is contradictory if its condition is a contradiction;
$P_{\bar{\tau}}$ is a contradiction, if $\forall x,\,P_{\bar{\tau}}(x)=\bot$.

Lemma Both $\tau$ and $\bar{\tau}$ are expressible.

Proof Because $P_{\tau}$ and $P_{\bar{\tau}}$ are effectively calculable, see
§3.1.6 and §3.1.5. $\diamond$

§3.1.12 Theorem $\left<{\xiibb P},\lor,\land,\neg,\bar{\tau},\tau\right>$ is a
Boolean algebra, where $\bar{\tau}$ is the neutral for $\lor$, and $\tau$ is
the neutral for $\land$.

Proof Because $P_{\pi}(x)\in{\xiibb B}$. In detail,
$\forall\pi,\rho,\sigma\in{\xiibb P}$:

1o. $(\pi\lor\rho)\lor\sigma=x?P_{\pi\lor\rho}(x)\lor
P_{\sigma}(x)=x?(P_{\pi}(x)\lor P_{\rho}(x))\lor
P_{\sigma}(x)=\hfil\break\hbox{}\hfill x?P_{\pi}(x)\lor(P_{\rho}(x)\lor
P_{\sigma}(x))=x?P_{\pi}(x)\lor
P_{\rho\lor\sigma}(x)=\pi\lor(\rho\lor\sigma)$.

1a. $(\pi\land\rho)\land\sigma=x?P_{\pi\land\rho}(x)\land
P_{\sigma}(x)=x?(P_{\pi}(x)\land P_{\rho}(x))\land
P_{\sigma}(x)=\hfil\break\hbox{}\hfill x?P_{\pi}(x)\land(P_{\rho}(x)\land
P_{\sigma}(x))=x?P_{\pi}(x)\land
P_{\rho\land\sigma}(x)=\pi\land(\rho\land\sigma)$.

2o. $\pi\lor\rho=x?P_{\pi}(x)\lor P_{\rho}(x)=x?P_{\rho}(x)\lor
P_{\pi}(x)=\rho\lor\pi$.

2a. $\pi\land\rho=x?P_{\pi}(x)\land P_{\rho}(x)=x?P_{\rho}(x)\land
P_{\pi}(x)=\rho\land\pi$.

3o. $\pi\lor\bar{\tau}=x?P_{\pi}(x)\lor
P_{\bar{\tau}}(x)=x?P_{\pi}(x)\lor\bot=x?P_{\pi}(x)=\pi$.

3a. $\pi\land\tau=x?P_{\pi}(x)\land
P_{\tau}(x)=x?P_{\pi}(x)\land\top=x?P_{\pi}(x)=\pi$.

4o. $\pi\lor\bar{\pi}=x?P_{\pi}(x)\lor P_{\bar{\pi}}(x)=x?P_{\pi}(x)\lor\neg
P_{\pi}(x)=x?\top=x?P_{\tau}(x)=\tau$.

4a. $\pi\land\bar{\pi}=x?P_{\pi}(x)\land
P_{\bar{\pi}}(x)=x?P_{\pi}(x)\land\neg
P_{\pi}(x)=x?\bot=x?P_{\bar{\tau}}(x)=\bar{\tau}$.

5o. $\pi\lor(\rho\land\sigma)=x?P_{\pi}(x)\lor
P_{\rho\land\sigma}(x)=x?P_{\pi}(x)\lor(P_{\rho}(x)\land
P_{\sigma}(x))=\hfil\break\hbox{}\hfill x?(P_{\pi}(x)\lor
P_{\rho}(x))\land(P_{\pi}(x)\lor P_{\sigma}(x))=x?P_{\pi\lor\rho}(x)\land
P_{\pi\lor\sigma}(x)=(\pi\lor\rho)\land(\pi\lor\sigma)$.

5a. $\pi\land(\rho\lor\sigma)=x?P_{\pi}(x)\land
P_{\rho\lor\sigma}(x)=x?P_{\pi}(x)\land(P_{\rho}(x)\lor
P_{\sigma}(x))=\hfil\break\hbox{}\hfill x?(P_{\pi}(x)\land
P_{\rho}(x))\lor(P_{\pi}(x)\land P_{\sigma}(x))=x?P_{\pi\land\rho}(x)\lor
P_{\pi\land\sigma}(x)=(\pi\land\rho)\lor(\pi\land\sigma)$.

$\diamond$

§3.2 Solutions

§3.2.1 Theorem Everything is in $\xiibb S$. In other words, $\xiibb S$ is the
set of everything.

Proof Anything, let us call it $s$, is a solution to problem $x?[x=s]$,
because equality is reflexive, and therefore everything satisfies the
condition of being equal to itself. $\diamond$

Comment Freedom is complete, because $x$ is free to take any value;
$x\in{\xiibb S}$ is not a restriction. And $P_{\pi}:{\xiibb S}\to{\xiibb B}$
is a predicate on everything.

Comment Some paradoxes derive from this theorem, see §3.2.12. For a
constructive vision of ${\xiibb S}$, see Section §5. See also Subsection §6.2.

Corollary ${\xiibb P}\subset\xiibb S$ and ${\xiibb R}\subset{\xiibb S}$. Even
${\xiibb B}\subset{\xiibb S}$.

Comment If you are a teacher looking for a problem to ask in an exam, then
your solution is a problem, so ${\xiibb P}\subset{\xiibb S}$ makes sense. And
if you are a mathematician looking for an algorithm to resolve some kind of
problems, then your solution is a resolution, so ${\xiibb R}\subset{\xiibb S}$
makes sense. There are many yes-or-no questions, so ${\xiibb B}\subset{\xiibb
S}$ makes sense.

§3.2.2 Notation Let $\Sigma_{\pi}$ be the (possibly infinite) set of all the
solutions to problem $\pi$. So $\Sigma_{\pi}\subseteq{\xiibb S}$, or
$\Sigma_{\pi}\in 2^{\xiibb S}$, and $\Sigma_{\pi}=\\{\,s\mid P_{\pi}(s)\,\\}$.

Comment A solution of the problem is any use of freedom that satisfies the
condition, see Section §2, so $s$ is a solution of problem $\pi$, if
$P_{\pi}(s)$ stands.

Comment The condition of the problem $\pi$ is the characteristic function of
its set of solutions, that is, $P_{\pi}$ is the characteristic function of
$\Sigma_{\pi}$.

§3.2.3 Lemma $\Sigma_{\pi\lor\rho}=\Sigma_{\pi}\cup\Sigma_{\rho}$, and
$\Sigma_{\pi\land\rho}=\Sigma_{\pi}\cap\Sigma_{\rho}$, and
$\Sigma_{\bar{\pi}}=\overline{\Sigma_{\pi}}$.

Proof Just apply the definitions in §3.1.10: $\Sigma_{\pi\lor\rho}=\\{\,s\mid
P_{\pi\lor\rho}(s)\,\\}=\\{\,s\mid P_{\pi}(s)\lor P_{\rho}(s)\,\\}=\\{\,s\mid
s\in\Sigma_{\pi}\lor s\in\Sigma_{\rho}\,\\}=\Sigma_{\pi}\cup\Sigma_{\rho}$.
$\Sigma_{\pi\land\rho}=\\{\,s\mid P_{\pi\land\rho}(s)\,\\}=\\{\,s\mid
P_{\pi}(s)\land P_{\rho}(s)\,\\}=\\{\,s\mid s\in\Sigma_{\pi}\land
s\in\Sigma_{\rho}\,\\}=\Sigma_{\pi}\cap\Sigma_{\rho}$.
$\Sigma_{\bar{\pi}}=\\{\,s\mid P_{\bar{\pi}}(s)\,\\}=\\{\,s\mid\neg
P_{\pi}(s)\,\\}=\\{\,s\mid s\notin\Sigma_{\pi}\,\\}=\overline{\Sigma_{\pi}}$.
$\diamond$

§3.2.4 Lemma For a tautological problem, $x?P_{\tau}(x)$, everything is a
solution, $\Sigma_{\tau}={\xiibb S}$. For a contradictory problem,
$x?P_{\bar{\tau}}(x)$, nothing is a solution, $\Sigma_{\bar{\tau}}=\emptyset$.

Proof $\Sigma_{\tau}=\\{\,s\mid P_{\tau}(s)\,\\}=\\{\,s\mid\top\,\\}={\xiibb
S}$. $\Sigma_{\bar{\tau}}=\\{\,s\mid
P_{\bar{\tau}}(s)\,\\}=\\{\,s\mid\bot\,\\}=\\{\\}=\emptyset$. $\diamond$

§3.2.5 Lemma $\Sigma_{\pi}\cup\Sigma_{\bar{\pi}}={\xiibb S}$ and
$\Sigma_{\pi}\cap\Sigma_{\bar{\pi}}=\emptyset$.

Proof $\Sigma_{\pi}\cup\Sigma_{\bar{\pi}}=\\{\,s\mid
P_{\pi}(s)\,\\}\cup\\{\,s\mid\neg P_{\pi}(s)\,\\}=\\{\,s\mid
P_{\pi}(s)\lor\neg P_{\pi}(s)\,\\}=\\{\,s\mid\top\,\\}={\xiibb S}$.
$\Sigma_{\pi}\cap\Sigma_{\bar{\pi}}=\\{\,s\mid
P_{\pi}(s)\,\\}\cap\\{\,s\mid\neg P_{\pi}(s)\,\\}=\\{\,s\mid
P_{\pi}(s)\land\neg P_{\pi}(s)\,\\}=\\{\,s\mid\bot\,\\}=\emptyset$. $\diamond$

§3.2.6 Lemma The solutions of $\pi\land\rho$ are solutions of $\pi$ and of
$\rho$.

Proof $\forall s\in{\xiibb
S};\;s\in\Sigma_{\pi\land\rho}\;\Leftrightarrow\;s\in\Sigma_{\pi}\cap\Sigma_{\rho}\;\Leftrightarrow\;s\in\Sigma_{\pi}\land
s\in\Sigma_{\rho}$. $\diamond$

Comment The reader is free to explore this Boolean landscape, but here we will
close with the following theorems.

§3.2.7 Theorem $\langle 2^{\xiibb S},\cup,\cap,-,\emptyset,{\xiibb S}\rangle$
is a Boolean algebra, where $\emptyset$ is the neutral for $\cup$, and $\xiibb
S$ is the neutral for $\cap$.

Proof The powerset of a set $M$, with the operations of union $\cup$,
intersection $\cap$, and complement with respect to set $M$, noted
$\overline{Q}$, is a typical example of a Boolean algebra. In detail, $\forall
Q,R,S\in 2^{\xiibb S}$:

1o. $(Q\cup R)\cup S=Q\cup(R\cup S)$. 1a. $(Q\cap R)\cap S=Q\cap(R\cap S)$.

2o. $Q\cup R=R\cup Q$. 2a. $Q\cap R=R\cap Q$.

3o. $Q\cup\emptyset=Q$. 3a. $Q\cap{\xiibb S}=Q$.

4o. $Q\cup\overline{Q}={\xiibb S}$. 4a. $Q\cap\overline{Q}=\emptyset$.

5o. $Q\cup(R\cap S)=(Q\cup R)\cap(Q\cup S)$. 5a. $Q\cap(R\cup S)=(Q\cap
R)\cup(Q\cap S)$. $\diamond$

§3.2.8 Theorem $\left<{\xiibb P},\lor,\land,\neg,\bar{\tau},\tau\right>$ is
isomorphic to $\langle 2^{\xiibb S},\cup,\cap,-,\emptyset,{\xiibb S}\rangle$,
that is, ${\xiibb P}\cong 2^{\xiibb S}$.

Proof We define the bijection $\Sigma$ that relates each problem $\pi$ with
the set of its solutions $\Sigma_{\pi}$: for every problem $\pi\in{\xiibb P}$
there is a set, the set of its solutions, $\Sigma_{\pi}\in 2^{\xiibb S}$, and
for every set $S\in 2^{\xiibb S}$ there is a problem, $\pi_{S}=x?[x\in S]$,
where $\pi_{S}\in{\xiibb P}$. Now, by Lemma §3.2.3, the bijection translates
properly all three operations, $\lor\leftrightarrow\cup$,
$\land\leftrightarrow\cap$, $\neg\leftrightarrow-$, and, by Lemma §3.2.4, also
the two neutrals, $\bar{\tau}\leftrightarrow\emptyset$,
$\tau\leftrightarrow{\xiibb S}$. $\diamond$

Comment We will call ${\xiibb P}\cong 2^{\xiibb S}$ the set isomorphism. That
is, ${\xiibb P}\Leftrightarrow 2^{\xiibb S}:\pi\leftrightarrow\Sigma_{\pi}$.

Comment Using the set isomorphism, two problems are equal if they have the
same solutions, that is, $\pi=\rho\Leftrightarrow\Sigma_{\pi}=\Sigma_{\rho}$.

§3.2.9 Theorem The set of problems is equal to the powerset of the solutions,
that is, ${\xiibb P}=2^{\xiibb S}$.

Proof The equality ${\xiibb P}=2^{\xiibb S}$ derives directly from the set
isomorphism ${\xiibb P}\cong 2^{\xiibb S}$, see §3.2.8, because no property
was abstracted out. $\diamond$

§3.2.10 Definition The set of singletons is: ${\xiibb S}^{1}=\\{\,S\in
2^{\xiibb S}\mid[\,|S|=1\,]\,\\}$.

Proposition ${\xiibb S}^{1}\subset 2^{\xiibb S}$, because $\forall S\in{\xiibb
S}^{1}$, $S\in 2^{\xiibb S}$, but $\emptyset\in 2^{\xiibb S}$ and
$\emptyset\notin{\xiibb S}^{1}$.

§3.2.11 Definition The singleton isomorphism is the isomorphism between
${\xiibb S}$ and ${\xiibb S}^{1}$ that relates each $s\in{\xiibb S}$ to the
set $\\{s\\}\in{\xiibb S}^{1}$, and the converse. That is, ${\xiibb
S}\cong{\xiibb S}^{1}$, and ${\xiibb S}\Leftrightarrow{\xiibb
S}^{1}:s\leftrightarrow\\{s\\}$.

Comment We can extend any operation on $\xiibb S$ to ${\xiibb S}^{1}$. For
example, for any binary operation $*$ on $\xiibb S$, we define
$\\{a\\}*\\{b\\}=\\{a*b\\}$.

Comment From the singleton isomorphism: ${\xiibb S}\cong{\xiibb S}^{1}\subset
2^{\xiibb S}$.

§3.2.12 Lemma The set of solutions ${\xiibb S}$ is a proper subset of the set
of problems ${\xiibb P}$, that is, ${\xiibb S}\subset{\xiibb P}$.

Proof By the singleton isomorphism, see §3.2.11, ${\xiibb S}\cong{\xiibb
S}^{1}$, and, by the set isomorphism, see §3.2.8, for each singleton there is
a problem, so ${\xiibb S}^{1}\subset{\xiibb P}$, and then ${\xiibb
S}\cong{\xiibb S}^{1}\subset{\xiibb P}$. $\diamond$

Paradox We have both, ${\xiibb S}\subset{\xiibb P}$ and, by §3.2.1, ${\xiibb
P}\subset{\xiibb S}$.

Comment If we only accept computable functions and computable sets, then
${\xiibb S}^{*}\not\subset{\xiibb P}^{*}$, see Subsection §6.2.

§3.2.13 Definition A problem $\pi$ is solved if a solution of $\pi$ is known.

Comment To solve a problem, given the set of its solutions $\Sigma_{\pi}$, a
choice function $f_{c}:2^{\xiibb S}\setminus\emptyset\to{\xiibb S}$ is needed.

§3.2.14 Definition A problem is unsolvable if $\Sigma_{\pi}=\\{\\}=\emptyset$,
that is, if $|\Sigma_{\pi}|=0$. A problem is solvable if $|\Sigma_{\pi}|>0$.

Comment If a problem has not any solution, then it is unsolvable. If a problem
has a solution, then it can be solved. A problem is solvable if it can be
solved.

Comment Solved implies solvable, but not the converse:
$\hbox{Solved}\Rightarrow\hbox{Solvable}$.

§3.3 Routines and Trials

§3.3.1 Definition We will refer to the routine of problem $\pi$ as $R_{\pi}$.
The routine is the set of the solutions to the problem, a set that is known,
see §2.3. Then $R_{\pi}=\Sigma_{\pi}$.

Comment The routine of problem $\pi$, $R_{\pi}$, is then, or an extensive
definition of $\Sigma_{\pi}$, $\Sigma_{\pi}=\\{s_{1},\dots,s_{n}\\}$, or a
procedure $\cal P$ that generates all problem $\pi$ solutions and then halts.
If the number of solutions is infinite, $|\Sigma_{\pi}|\geq\aleph_{0}$, then
$R_{\pi}$ has to be a procedure $\cal P$ that keeps generating solutions
forever.

§3.3.2 Definition A trial on problem $\pi$ over the set of possible solutions
$S$, written $T_{\pi}(S)$, returns the set of those elements in $S$ that
satisfy the problem condition $P_{\pi}$, see §2.3. Then $T_{\pi}(S)=\\{\,s\in
S\mid P_{\pi}(s)\,\\}$.

Comment Mathematically we will ignore the practical problem of governing the
trial. Practically we will need a halt condition to truncate the calculations
that are too long (or infinite), and some ordering on the tests to fit the
execution of the tests to the available calculating machinery.

§3.3.3 Definition To test if a possible solution $s\in S$ is a solution to
problem $\pi$, is to replace the free variable with $s$. So, being
$\pi=x?P_{\pi}(x)$, then to test if $s$ is a solution is to calculate
$P_{\pi}(s)$.

Comment Testing is a calculation ${\xiibb S}\to{\xiibb B}$.

§3.3.4 Remark Replacing variables in expressions requires not confusing free
with bound variables, nor bound with free variables.

Comment This means that the rule of $\beta$-conversion and the rules $\gamma$
for substitution stand for testing. See Curry & Feys (1958), Section 3D for
$\beta$-conversion, and Section 3E for substitution (the rules $\gamma$).

§3.3.5 Theorem A trial on problem $\pi$ over the set $S$ is equal to the
intersection of $S$ with the set of the solutions $\Sigma_{\pi}$, that is,
$T_{\pi}(S)=S\cap\Sigma_{\pi}$.

Proof $T_{\pi}(S)=\\{\,s\in S\mid P_{\pi}(s)\,\\}=\\{\,s\mid s\in S\land
P_{\pi}(s)\,\\}=\\{\,s\mid s\in S\land
s\in\Sigma_{\pi}\,\\}=\hbox{}\hfil\break\\{\,s\mid s\in S\,\\}\cap\\{\,s\mid
s\in\Sigma_{\pi}\,\\}=S\cap\Sigma_{\pi}$. $\diamond$

Corollary Any trial is a subset of the set of solutions,
$T_{\pi}(S)\subseteq\Sigma_{\pi}$.

Proof $T_{\pi}(S)=S\cap\Sigma_{\pi}\subseteq\Sigma_{\pi}$. $\diamond$

Corollary Any trial is a subset of the routine, that is,
$T_{\pi}(S)\subseteq\Sigma_{\pi}=R_{\pi}$.

§3.3.6 Lemma If $S$ is a superset of $\Sigma_{\pi}$, then a trial on problem
$\pi$ over $S$ is equal to $\Sigma_{\pi}$, and the converse, that is,
$\Sigma_{\pi}\subseteq S\Leftrightarrow T_{\pi}(S)=\Sigma_{\pi}$.

Proof $\Sigma_{\pi}\subseteq S\Leftrightarrow
S\cap\Sigma_{\pi}=\Sigma_{\pi}\Leftrightarrow T_{\pi}(S)=\Sigma_{\pi}$, using
Theorem §3.3.5. $\diamond$

Corollary If $S$ is a superset of $\Sigma_{\pi}$, then a trial on problem
$\pi$ over $S$ is equal to the routine of $\pi$, and the converse, that is,
$\Sigma_{\pi}\subseteq S\Leftrightarrow T_{\pi}(S)=R_{\pi}$.

Proof $\Sigma_{\pi}\subseteq S\Leftrightarrow
S\cap\Sigma_{\pi}=\Sigma_{\pi}\Leftrightarrow T_{\pi}(S)=R_{\pi}$. $\diamond$

Corollary A trial on problem $\pi$ over the whole ${\xiibb S}$ is equal to
$\Sigma_{\pi}$, that is, $T_{\pi}({\xiibb S})=\Sigma_{\pi}$.

Proof Because $\Sigma_{\pi}\subseteq{\xiibb S}$. $\diamond$

Comment $T_{\pi}({\xiibb S})$ is an exhaustive search.

§3.3.7 Theorem The routine is a trial over all the solutions, that is,
$R_{\pi}=T_{\pi}(\Sigma_{\pi})$.

Proof By Theorem §3.3.5,
$T_{\pi}(\Sigma_{\pi})=\Sigma_{\pi}\cap\Sigma_{\pi}=\Sigma_{\pi}=R_{\pi}$.
$\diamond$

Comment $T_{\pi}(R_{\pi})=T_{\pi}(\Sigma_{\pi})=\Sigma_{\pi}=R_{\pi}$.

§3.4 Analogies

§3.4.1 Definition If $A$ is an analogy, and $\pi=x?P_{\pi}(x)$ is a problem,
then $A\pi$ is another problem $A\pi=x?P_{\\!A\pi}(x)$. That is, $A:{\xiibb
P}\to{\xiibb P}$.

Comment So analogies transform a condition into a condition, $P_{\pi}$ into
$P_{\\!A\pi}$ in this example.

Comment Taking advantage of problem decomposition, see §3.1.10, the result of
an analogy, $A\pi$, can be a composition of problems that are easier to
resolve than the original problem, $\pi$, see §2.3.

§3.4.2 Definition If $\Sigma_{\pi}=\Sigma_{A\pi}$, then we say that the
analogy is conservative.

Comment If an analogy is not conservative, then a function ${\cal T}_{A}$ to
translate $\Sigma_{A\pi}$ to $\Sigma_{\pi}$ is required, because otherwise the
analogy would be useless.

§3.4.3 Notation We will call function ${\cal T}_{A}$ the translating function
of analogy $A$. ${\cal T}_{A}:2^{\xiibb S}\to 2^{\xiibb S}$ and ${\cal
T}_{A}(\Sigma_{A\pi})=\Sigma_{\pi}$.

§3.4.4 Lemma An analogy followed by another one is an analogy.

Proof Because any analogy transforms a problem into a problem: ${\xiibb
P}\to{\xiibb P}$. $\diamond$

Corollary Analogies can be chained.

§3.4.5 Lemma Using only analogies we cannot resolve any problem.

Proof Because using analogies we only get problems. $\diamond$

Comment While routines $R$ and trials $T(S)$ are functions that return a set,
${\xiibb P}\to 2^{\xiibb S}$, analogies $A$ are functions that return a
function, ${\xiibb P}\to{\xiibb P}$.

§3.4.6 Notation We will write $A\circ T$ to express the composition of
functions, where $A$ is applied first and then $T$.

Comment $[A\circ T](x)=T(A(x))$. Diagram: $x\mathop{\hbox
to18.3pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle A$}}A(x)\mathop{\hbox
to18.07542pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle T$}}T(A(x))$.

Comment If $A_{1}$ and $A_{2}$ are analogies, then $A_{1}\circ A_{2}$ is also
an analogy, by Lemma §3.4.4.

§3.4.7 Definition To resolve a problem by analogy $A$ is to compose
$A\circ\Re\circ{\cal T}_{A}$, where $\Re$ is any resolution, and ${\cal
T}_{A}$ is the translating function of $A$. Diagrams:

${\pi}\mathop{\hbox to18.3pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle
A$}}{A\pi}\mathop{\hbox
to18.06668pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\Re$}}{\Sigma_{A\pi}}\mathop{\hbox
to21.66669pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle{\cal
T}_{A}$}}{\Sigma_{\pi}}\qquad\hbox{or}\qquad{\xiibb P}\mathop{\hbox
to18.3pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle A$}}{\xiibb
P}\mathop{\hbox
to18.06668pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\Re$}}2^{\xiibb
S}\mathop{\hbox
to21.66669pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle{\cal
T}_{A}$}}2^{\xiibb S}\;.$

Comment Analogy $A$ is a translation from some original problem domain to some
analogue problem domain. Then, by Lemma §3.4.5, we need a resolution $\Re$ to
resolve the analogue problem. And, finally, we need to translate the solutions
back to the original domain.

§3.4.8 Lemma The translating function of the composition $A\circ A^{\prime}$
is ${\cal T}_{A^{\prime}}\circ{\cal T}_{A}$.

Proof If $\Re=A^{\prime}\circ\Re^{\prime}\circ{\cal T}_{A^{\prime}}$ then we
get $A\circ(A^{\prime}\circ\Re^{\prime}\circ{\cal T}_{A^{\prime}})\circ{\cal
T}_{A}=A\circ A^{\prime}\circ\Re^{\prime}\circ{\cal T}_{A^{\prime}}\circ{\cal
T}_{A}=(A\circ A^{\prime})\circ\Re^{\prime}\circ({\cal
T}_{A^{\prime}}\circ{\cal T}_{A})$, because function composition is
associative. Diagram:

${\xiibb P}\mathop{\hbox
to18.3pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle A$}}\underbrace{{\xiibb
P}\mathop{\hbox to19.62pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle
A^{\prime}$}}{\xiibb P}\mathop{\hbox
to19.38667pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\Re^{\prime}$}}2^{\xiibb
S}\mathop{\hbox
to22.72267pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle{\cal
T}_{A^{\prime}}$}}2^{\xiibb S}}_{\Re}\mathop{\hbox
to21.66669pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle{\cal
T}_{A}$}}2^{\xiibb S}.\quad{\diamond}$

Corollary The translating function of the composition $A_{1}\circ
A_{2}\dots\circ A_{n}$ is ${\cal T}_{A_{n}}\circ\dots\circ{\cal
T}_{A_{2}}\circ{\cal T}_{A_{1}}$. That is: ${\cal T}_{A_{1}\circ
A_{2}\dots\circ A_{n}}={\cal T}_{A_{n}}\circ\dots\circ{\cal
T}_{A_{2}}\circ{\cal T}_{A_{1}}$.

Comment This is how analogies can be chained.

§3.4.9 Definition The identity function, written $I$, transforms anything into
itself: $\forall x,\;I(x)=x$.

Comment The identity function $I$ is an effectively calculable function, see
§3.1.5. It is $\lambda$-definable; in $\lambda$-calculus, $I=(\lambda x.x)$.

Comment Identity $I$ transforms $\pi$ into $\pi$, $I(\pi)=\pi$, and $P_{\pi}$
into $P_{\pi}$, $I(P_{\pi})=P_{\pi}$.

Comment Identity $I$ can work as an analogy: $I\pi=I(\pi)=\pi$.

§3.4.10 Lemma The translating function of the identity analogy is the identity
function: ${\cal T}_{I}=I$.

Proof Because $I(\Sigma_{\pi})=\Sigma_{\pi}$. Diagram: $\pi\mathop{\hbox
to16.35165pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle
I$}}\pi\mathop{\hbox
to18.06668pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\Re$}}\Sigma_{\pi}\mathop{\hbox
to16.35165pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle I$}}\Sigma_{\pi}$.
$\diamond$

Comment The identity analogy is conservative, see §3.4.2.

§3.4.11 Lemma The identity $I$ followed by any function $f$, or any function
$f$ followed by identity $I$, is equal to the function: $\forall f,\;I\circ
f=f=f\circ I$.

Proof $\forall f,\forall x,\;[I\circ f](x)=f(I(x))=f(x)=I(f(x))=[f\circ
I](x)$. $\diamond$

Comment $I\circ\Re(I\pi)\circ{\cal T}_{I}=I\circ\Re(\pi)\circ I=\Re(\pi)$.

§3.4.12 Theorem $A\circ{T\\!}_{A\pi}(S)\circ{\cal T}_{A}$, where $A$ is an
analogy, ${T\\!}_{A\pi}(S)$ is a trial, and ${\cal T}_{A}$ is the translating
function of $A$, is the general form of a resolution.

Proof If the analogy is the identity $I$, then the general form is reduced to
$T_{\pi}(S)$, because ${\cal T}_{I}=I$, $I\pi=\pi$, so $I\circ
T_{I\pi}(S)\circ I=T_{\pi}(S)$, which is a trial. By Theorem §3.3.7, a routine
is a specific trial, $R_{\pi}=T_{\pi}(R_{\pi})$, so $I\circ
T_{\pi}(R_{\pi})\circ I=T_{\pi}(R_{\pi})=R_{\pi}$ reduces the general form to
the routine. Resolving by analogy is, by definition, $A\circ\Re\circ{\cal
T}_{A}$, and analogies can be chained, by Lemma §3.4.4, so a chain of
analogies is an analogy, $A_{1}\circ A_{2}\circ\dots\circ A_{n}=A$, and by
Lemma §3.4.8, ${\cal T}_{A}={\cal T}_{A_{1}\circ A_{2}\circ\dots\circ
A_{n}}={\cal T}_{A_{n}}\circ\dots\circ{\cal T}_{A_{2}}\circ{\cal T}_{A_{1}}$.
Then $A_{1}\circ A_{2}\circ\dots\circ A_{n}\circ{T\\!}_{A\pi}(S)\circ{\cal
T}_{A_{n}}\circ\dots\circ{\cal T}_{A_{2}}\circ{\cal
T}_{A_{1}}=A\circ{T\\!}_{A\pi}(S)\circ{\cal T}_{A}$. $\diamond$

Summary There are three ways to resolve a problem: routine $R_{\pi}=I\circ
T_{\pi}(R_{\pi})\circ I$, trial $T_{\pi}(S)=I\circ T_{\pi}(S)\circ I$, and
analogy $A_{1}\circ\dots\circ A_{n}\circ{T\\!}_{A\pi}(S)\circ{\cal
T}_{A_{n}}\circ\dots\circ{\cal T}_{A_{1}}=A\circ{T\\!}_{A\pi}(S)\circ{\cal
T}_{A}$.

§3.5 Metaproblems

§3.5.1 Definition A resolution $\Re:{\xiibb P}\to 2^{\xiibb S}$ is a valid
resolution for a problem $\pi$ if it finds all the solutions of problem $\pi$
and then halts. In other words, $\Re$ is a valid resolution for $\pi$ if it
satisfies two conditions: that $\Re(\pi)$ is effectively calculable, and that
$\Re$ fits problem $\pi$, that is, that $\Re(\pi)=\Sigma_{\pi}$.

Comment If $\Sigma_{\pi}$ is infinite, $|\Sigma_{\pi}|\geq\aleph_{0}$, then a
valid $\Re(\pi)$ does not halt, but it keeps building $\Sigma_{\pi}$ forever.

§3.5.2 Definition A problem $\pi$ is resolved if a valid resolution for $\pi$
is known.

Comment To solve a problem we have to find one solution, see §3.2.13. To
resolve a problem we have to find all the solutions. To resolve a problem is
to exhaust the problem.

§3.5.3 Lemma Once a problem is resolved, we can thereafter resolve it by
routine.

Proof Once a problem is resolved, we know all of its solutions,
$\Sigma_{\pi}$, and knowing $\Sigma_{\pi}$, we know its routine resolution,
because $R_{\pi}=\Sigma_{\pi}$, see §3.3.1. $\diamond$

Proposition If $\pi\land\rho$ is solvable, then by resolving $\pi\land\rho$
both $\pi$ and $\rho$ are solved.

§3.5.4 Definition A problem is resolvable if there is a valid resolution for
the problem, see §3.5.1, that is, if there is a resolution $\Re$ such that
$\Re(\pi)$ is effectively calculable, and $\Re(\pi)=\Sigma_{\pi}$. Otherwise,
the problem is unresolvable.

Comment A problem is resolvable if it can be resolved.

Comment Resolved implies resolvable, but not the converse:
$\hbox{Resolved}\Rightarrow\hbox{Resolvable}$.

§3.5.5 Definition For any Boolean-valued function $P:{\xiibb S}\to{\xiibb B}$,
we define the function $\check{P}:{\xiibb B}\to 2^{\xiibb S}$, called the
inverse of condition $P$, as follows:

$\eqalign{\check{P}(\top)&=\\{\,x\mid[P(x)=\top]\,\\},\cr\check{P}(\bot)&=\\{\,x\mid[P(x)=\bot]\,\\}.\cr}$

§3.5.6 Lemma If $P_{\pi}(x)$ is the condition of a problem $\pi$, then
$\check{P}_{\pi}(\top)=\Sigma_{\pi}$ and
$\check{P}_{\pi}(\bot)=\overline{\Sigma_{\pi}}=\Sigma_{\bar{\pi}}$.

Proof Because
$\check{P}_{\pi}(\top)=\\{\,x\mid[P_{\pi}(x)=\top]\,\\}=\\{\,x\mid
P_{\pi}(x)\,\\}=\Sigma_{\pi}$, and
$\check{P}_{\pi}(\bot)=\\{\,x\mid[P_{\pi}(x)=\bot]\,\\}=\\{\,x\mid\neg
P_{\pi}(x)\,\\}=\overline{\Sigma_{\pi}}=\Sigma_{\bar{\pi}}$, by Lemma §3.2.3.
$\diamond$

§3.5.7 Theorem The inverse of the condition of a problem, provided it is an
effectively calculable function, resolves the problem and its complementary by
routine.

Proof By §3.5.6 and §3.3.1, $\check{P}_{\pi}(\top)=\Sigma_{\pi}=R_{\pi}$, then
$\check{P}_{\pi}(\top)$ is the routine resolution of $\pi$, if
$\check{P}_{\pi}(\top)$ is effectively calculable, see §3.1.5. And if
$\check{P}_{\pi}(\bot)$ is effectively calculable, then it resolves the
complementary problem by routine,
$\check{P}_{\pi}(\bot)=\Sigma_{\bar{\pi}}=R_{\bar{\pi}}$. $\diamond$

Comment It is a nice theorem, but how can we find the inverse of a condition?

§3.5.8 Definition The metaproblem of a problem, written $\Pi\pi$, is the
problem of finding the valid resolutions for problem $\pi$. In other words, if
$\pi=x?P_{\pi}(x)$, then $\Pi\pi=\Re?[\Re(\pi)=\Sigma_{\pi}]$.

Comment The solutions of the metaproblems are the resolutions, $\Pi{\xiibb
S}={\xiibb R}$.

Comment The condition of the metaproblem, $P_{\Pi\pi}$, is
$[\Re(\pi)=\Sigma_{\pi}]$, that is, $P_{\Pi\pi}(\Re)=[\Re(\pi)=\Sigma_{\pi}]$,
or using an $\alpha$-conversion, $P_{\Pi\pi}(x)=[x(\pi)=\Sigma_{\pi}]$.

§3.5.9 Lemma A metaproblem is a problem, that is, $\Pi{\xiibb P}\subset{\xiibb
P}$.

Proof Because $\Pi\pi=x?P_{\Pi\pi}(x)$, but some problems are not
metaproblems. $\diamond$

Comment A metaproblem is a problem because it has its two ingredients: there
are several ways to resolve a problem, so there is freedom, but only the valid
resolutions resolve the problem, so there is a condition.

§3.5.10 Definition The metacondition $P_{\Pi}$ is
$P_{\Pi}(p,r)=[r(p)=\Sigma_{p}]$, for any problem $p\in{\xiibb P}$, and for
any resolution $r\in{\xiibb R}$.

Comment Using another $\alpha$-conversion,
$P_{\Pi}(\pi,x)=[x(\pi)=\Sigma_{\pi}]=P_{\Pi\pi}(x)$.

Comment $\Pi\pi=x?P_{\Pi}(\pi,x)$.

§3.5.11 Definition Metaresolving is resolving the metaproblem to resolve the
problem.

Comment Metaresolving is a kind of analogy. Diagram:

${\pi}\mathop{\hbox
to18.3pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\Pi$}}{\Pi\pi}\mathop{\hbox
to24.36668pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\Pi\Re$}}{\Sigma_{\Pi\pi}}=\\{\,\Re\mid[\Re(\pi)=\Sigma_{\pi}]\,\\}\mathop{\hbox
to19.09392pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle
f_{c}$}}\Re_{c}\mathop{\hbox
to23.32158pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle(\pi)$}}\Re_{c}(\pi)=\Sigma_{\pi}\;.$

Function $f_{c}$ is a choice function, and the last calculation, noted
$(\pi)$, means to apply $\pi$ as the argument, not as the function. If you
only metasolve, then you don’t need to choose. In any case, the translating
function of metaresolving is ${\cal T}_{\Pi}=f_{c}\circ(\pi)$. Then we can
draw the following diagrams:

${\pi}\mathop{\hbox
to18.3pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\Pi$}}{\Pi\pi}\mathop{\hbox
to24.36668pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\Pi\Re$}}{\Sigma_{\Pi\pi}}\mathop{\hbox
to21.66669pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle{\cal
T}_{\Pi}$}}{\Sigma_{\pi}}\qquad\hbox{or}\qquad{\xiibb P}\mathop{\hbox
to18.3pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\Pi$}}\Pi{\xiibb
P}\mathop{\hbox
to24.36668pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\Pi\Re$}}2^{\Pi\xiibb
S}=2^{\xiibb R}\mathop{\hbox
to21.66669pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle{\cal
T}_{\Pi}$}}2^{\xiibb S}\;.$

§3.5.12 Lemma The metaproblem $\Pi\pi$ of some problem $\pi$ is solvable if,
and only if, the problem $\pi$ is resolvable, that is, $\Pi\pi\hbox{ is
solvable}\Leftrightarrow\pi\hbox{ is resolvable}$.

Proof If $\Pi\pi$ is solvable, then there is a solution to it, see §3.2.14,
and that solution is a valid resolution for $\pi$, see §3.5.8, and then $\pi$
is resolvable, see §3.5.4. If $\pi$ is resolvable, then there is a valid
resolution for it, see §3.5.4, and that resolution is a solution of its
metaproblem $\Pi\pi$, see §3.5.8, and then $\Pi\pi$ is solvable, see §3.2.14.
$\diamond$

Corollary To solve the metaproblem $\Pi\pi$ of problem $\pi$ is to resolve
problem $\pi$.

Proof Because to resolve problem $\pi$ is to find a valid resolution for
$\pi$, see §3.5.2, and to solve the metaproblem $\Pi\pi$ is to find a solution
to $\Pi\pi$, see §3.2.13, which is also to find a valid resolution for $\pi$,
see §3.5.8. $\diamond$

Comment And again, ${\xiibb R}=\Pi{\xiibb S}$.

§3.5.13 Lemma The set of the valid resolutions for problem $\pi$ is the
routine resolution of its metaproblem $\Pi\pi$, that is,
$\\{\,\Re\mid[\Re(\pi)=\Sigma_{\pi}]\,\\}=R_{\Pi\pi}$.

Proof $R_{\Pi\pi}=\Sigma_{\Pi\pi}$, by the definition of routine, see §3.3.1.
And $\Sigma_{\Pi\pi}=\\{\,\Re\mid[\Re(\pi)=\Sigma_{\pi}]\,\\}$, by the
definition of $\Pi\pi$, see §3.5.8. $\diamond$

§3.6 Resolution Typology

§3.6.1 Definition The metan-metaproblem of $\pi$, $\Pi^{n}\Pi\pi$, is (the
metaproblem of)n the metaproblem of $\pi$, where $n\in{\xiibb N}$.

Special case The meta-metaproblem of $\pi$, $\Pi\Pi\pi=\Pi^{1}\Pi\pi$, is the
metaproblem of the metaproblem of $\pi$.

Examples $\Pi^{0}\Pi\pi=\Pi\pi$. $\Pi^{1}\Pi\pi=\Pi\Pi\pi=\Pi^{2}\pi$.
$\Pi^{2}\Pi\pi=\Pi\Pi\Pi\pi=\Pi^{3}\pi$.

Comment From $\Pi{\xiibb S}={\xiibb R}$, we get $\Pi\Pi{\xiibb S}=\Pi{\xiibb
R}$ and $\Pi^{n}\Pi{\xiibb S}=\Pi^{n}{\xiibb R}$.

Comment The condition of the metan-metaproblem of $\pi$, $P_{\Pi^{n}\Pi\pi}$,
where $n\in{\xiibb N}$, is:
$P_{\Pi^{n}\Pi\pi}(x)=[x(\Pi^{n}\pi)=\Sigma_{\Pi^{n}\pi}]$.

Examples
$P_{\Pi^{0}\Pi\pi}(x)=[x(\Pi^{0}\pi)=\Sigma_{\Pi^{0}\pi}]=[x(\pi)=\Sigma_{\pi}]=P_{\Pi\pi}(x)$.
$P_{\Pi^{1}\Pi\pi}(x)=[x(\Pi^{1}\pi)=\Sigma_{\Pi^{1}\pi}]=[x(\Pi\pi)=\Sigma_{\Pi\pi}]=P_{\Pi\Pi\pi}(x)$.

§3.6.2 Lemma A metan-metaproblem is a problem, where $n\in{\xiibb N}$.

Proof If $n>0$, then $\Pi^{n}\Pi\pi=x?P_{\Pi^{n}\Pi\pi}(x)$. For $n=0$, see
§3.5.9. $\diamond$

Corollary $\bigcup_{n\in{\xiibb N}}\Pi^{n}\Pi{\xiibb P}\subset{\xiibb P}$.

§3.6.3 Definition The metan-metacondition $P_{\Pi^{n}\Pi}$, with $n\in{\xiibb
N}$, $p\in{\xiibb P}$, and $r\in{\xiibb R}$ is:
$P_{\Pi^{n}\Pi}(p,r)=[r(\Pi^{n}p)=\Sigma_{\Pi^{n}p}]$.

Comment Using an $\alpha$-conversion,
$P_{\Pi^{n}\Pi}(\pi,x)=[x(\Pi^{n}\pi)=\Sigma_{\Pi^{n}\pi}]=P_{\Pi^{n}\Pi\pi}(x)$.

Example
$P_{\Pi^{1}\Pi}(\pi,x)=P_{\Pi\Pi}(\pi,x)=[x(\Pi\pi)=\Sigma_{\Pi\pi}]=[x(\Pi^{1}\pi)=\Sigma_{\Pi^{1}\pi}]$.

§3.6.4 Lemma $P_{\Pi^{n}\Pi}(\pi,x)=P_{\Pi}(\Pi^{n}\pi,x)$, where $n\in{\xiibb
N}$.

Proof By §3.5.10,
$P_{\Pi}(\Pi^{n}\pi,x)=[x(\Pi^{n}\pi)=\Sigma_{\Pi^{n}\pi}]=P_{\Pi^{n}\Pi}(\pi,x)$.
$\diamond$

Special Case $P_{\Pi\Pi}(\pi,x)=P_{\Pi}(\Pi\pi,x)$.

Comment The meta-metacondition is the metacondition of the metaproblem.

§3.6.5 Lemma A metan-metaproblem is a metaproblem, where $n\in{\xiibb N}$.

Proof If $n>0$, $\Pi^{n}\Pi\pi=x?P_{\Pi}(\Pi^{n}\pi,x)$, and
$\Pi^{0}\Pi\pi=\Pi\pi=x?P_{\Pi}(\pi,x)$. $\diamond$

Corollary $\bigcup_{n\in{\xiibb N}}\Pi^{n}\Pi{\xiibb P}=\Pi{\xiibb P}$.

§3.6.6 Lemma We have the following infinite series of mathematical objects:
${\xiibb S}$, ${\xiibb P}=2^{\xiibb S}$, ${\xiibb R}=\Pi{\xiibb S}=2^{\xiibb
S}\to 2^{\xiibb S}$, $\Pi{\xiibb P}=2^{2^{\xiibb S}\to 2^{\xiibb S}}$,
$\Pi{\xiibb R}=\Pi\Pi{\xiibb S}=2^{2^{\xiibb S}\to 2^{\xiibb S}}\to
2^{2^{\xiibb S}\to 2^{\xiibb S}}$, $\dots$

Proof ${\xiibb P}={\xiibb S}\to{\xiibb B}=2^{\xiibb S}$, by Theorems §3.1.8
and §3.2.9. $\Pi{\xiibb S}={\xiibb R}$, by the metaproblem definition, see
§3.5.8, and ${\xiibb R}={\xiibb P}\to 2^{\xiibb S}=2^{\xiibb S}\to 2^{\xiibb
S}$. $\Pi{\xiibb P}=\Pi{\xiibb S}\to{\xiibb B}={\xiibb R}\to{\xiibb
B}=2^{\xiibb R}=2^{2^{\xiibb S}\to 2^{\xiibb S}}$. $\Pi{\xiibb R}=\Pi{\xiibb
P}\to 2^{\Pi{\xiibb S}}=2^{\xiibb R}\to 2^{\xiibb R}=2^{2^{\xiibb S}\to
2^{\xiibb S}}\to 2^{2^{\xiibb S}\to 2^{\xiibb S}}$. And so on. $\diamond$

§3.6.7 Theorem There is only one level of problem meta-ness.

Proof By Lemma §3.6.5, because every metan-metaproblem is a metaproblem, and
every metaproblem is a meta0-metaproblem, so $\bigcup_{n\in{\xiibb
N}}\Pi^{n}\Pi{\xiibb P}=\Pi{\xiibb P}\subset{\xiibb P}$. $\diamond$

Comment While a problem condition is any predicate, $P(x)$, a metaproblem
condition is a specific kind of predicate, namely,
$P_{\Pi}(p,r)=[r(p)=\Sigma_{p}]$. And any metan-metaproblem condition,
$P_{\Pi^{n}\Pi}$, is the same specific predicate $P_{\Pi}$, see §3.6.4.

Comment We are assuming that functions are free to take functions as
arguments. See that, in predicate $P_{\Pi}(p,r)=[r(p)=\Sigma_{p}]$, argument
$r$ is a function in $\Pi^{n}{\xiibb R}$ that takes $p\in\Pi^{n}{\xiibb P}$ as
argument. Therefore, the theorem holds unconditionally for $\lambda$-definable
functions, including predicates, see §4.2.9. And then, under Church’s thesis,
see §4.3.1, the theorem is true for effectively calculable functions, and in
particular, it is true for expressible and for resolvable problems, see §3.1.6
and §3.5.4.

§3.6.8 Theorem There are five types of resolution.

Proof From Theorem §3.4.12 we get three types for the resolution of problems:
$R_{\pi}$, $T_{\pi}(S)$, and $A\circ{T\\!}_{A\pi}(S)\circ{\cal T}_{A}$. This
shows that there are several ways of resolving, so choosing a resolution that
find solutions to the original problem $\pi$ is another problem, the
metaproblem $\Pi\pi$, see §3.5.8. Then we should get another three for the
resolution of the metaproblem, but, by §3.5.13, the set of the resolutions of
a problem is the routine resolution of its metaproblem, so we only add two
more for the metaproblem: $T_{\Pi\pi}(R)$, and ${\cal A}\circ{T\\!}_{{\cal
A}\Pi\pi}(R)\circ{\cal T}_{\cal A}$. Finally, by §3.6.7, we do not need to go
deeper into metan-metaproblems. $\diamond$

Comment We will call them: routine $R_{\pi}$, trial $T_{\pi}(S)$, analogy
$A\circ{T\\!}_{A\pi}(S)\circ{\cal T}_{A}$, meta-trial $T_{\Pi\pi}(R)$, and
meta-analogy ${\cal A}\circ{T\\!}_{{\cal A}\Pi\pi}(R)\circ{\cal T}_{\cal A}$.
The first three can also be called meta-routines.

§3.6.9 Remark The diagram for the meta-trial, or trial of the metaproblem, is:

${\pi}\mathop{\hbox
to18.3pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\Pi$}}{\Pi\pi}\mathop{\hbox
to37.38782pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle
T_{\Pi\pi}(R)$}}{\Sigma_{\Pi\pi}}\mathop{\hbox
to21.66669pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle{\cal
T}_{\Pi}$}}{\Sigma_{\pi}}\;.$

And the diagram for the meta-analogy, or analogy of the metaproblem, is:

${\pi}\mathop{\hbox
to18.3pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\Pi$}}{\Pi\pi}\mathop{\hbox
to18.3pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\cal A$}}{{\cal
A}\Pi\pi}\mathop{\hbox
to40.98782pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle T_{{\cal
A}\Pi\pi}(R)$}}\Sigma_{{\cal A}\Pi\pi}\mathop{\hbox
to21.66669pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle{\cal T}_{\cal
A}$}}\Sigma_{\Pi\pi}\mathop{\hbox
to21.66669pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle{\cal
T}_{\Pi}$}}\Sigma_{\pi}\;.$

See that ${\cal A}:\Pi{\xiibb P}\to\Pi{\xiibb P}=2^{2^{\xiibb S}\to 2^{\xiibb
S}}\to 2^{2^{\xiibb S}\to 2^{\xiibb S}}$ and ${\cal T}_{\cal A}:2^{\Pi{\xiibb
S}}\to 2^{\Pi{\xiibb S}}=2^{2^{\xiibb S}\to 2^{\xiibb S}}\to 2^{2^{\xiibb
S}\to 2^{\xiibb S}}$, using §3.6.6. Both are functions taking sets of
functions on sets to sets and returning sets of functions on sets to sets.

§4 Computers

§4.1 Turing Machine

§4.1.1 Definition A computation is any manipulation of a string of symbols,
irrespective of the symbols meanings, but according to a finite set of well-
defined rules.

Comment Computing is any mechanical transformation of a string of symbols.

§4.1.2 Definition A computing device, or computer, is any mechanism that can
perform computations.

Comment The prototype of computing device is a Turing machine, see Turing
(1936).

§4.1.3 Notation The Turing machine has two parts: the processor ${\cal P}$,
which is a finite state automaton, and an infinite tape,
$\langle{\xiifrak\;}\rangle$, which in any moment contains only a finite
number of symbols.

Comment In the case of a processor of a Turing machine, the output alphabet
$O$, that is, the finite set of output symbols, has to be:
$O=I^{+}\times\\{l,h,r\\}$, where $I$ is the finite not empty input alphabet,
$I^{+}=I\cup\\{b\\}$, where $b\notin I$ is blank, and $l$, $h$, and $r$ mean
left, halt, and right. Then its transition function is ${\cal T}:S\times
I^{+}\to S\times I^{+}\times\\{l,h,r\\}$, where $S$ is the finite set of
internal states. And the strings that the Turing machine transforms are
sequences of symbols taken from set $I$.

§4.1.4 Notation We will refer to the set of Turing machines as $\xiifrak T$.
We will refer to the set of the strings of symbols as $\xiifrak E$.

Comment Because all Turing machines tapes are equal, the processor defines the
Turing machine, and therefore we will refer to the Turing machine with
processor $\cal P$ as the Turing machine $\cal P$, and then $\cal P\in\xiifrak
T$. We will refer to the string of symbols written on the tape as the
expression $\xiifrak e\in E$.

§4.1.5 Lemma The set of expressions is countable, that is, $|{\xiifrak
E}|=|{\xiibb N}|={\aleph}_{0}$.

Proof Let $I$ be any finite alphabet, and $s$ its cardinality, that is, $s$ is
the number of symbols, $s=|I|>0$. We write $I^{n}$ the set of strings of
length $n$, so $|I^{n}|=s^{n}$. Then ${\xiifrak E}=\bigcup_{n\in{\xiibb
N}}I^{n}$, and we can define a bijection between ${\xiifrak E}$ and ${\xiibb
N}$ this way: it maps the empty string in $I^{0}$ to $0$, it maps the $s$
strings in $I^{1}$ to the next $s$ numbers, it maps the $s^{2}$ strings in
$I^{2}$ to the next $s^{2}$ numbers, and so on. Note that ordering the symbols
in $I$, we can order alphabetically the strings in each $I^{n}$. $\diamond$

Comment Most real numbers are not expressible. See Turing (1936) §10 for
details; but, for example, transcendental numbers $\pi$ and $e$ are
computable, page 256.

§4.1.6 Notation We will use the notation ${\cal P}\langle{\xiifrak
e}\rangle\hookrightarrow{\xiifrak r}$ to indicate that, if we write the
expression ${\xiifrak e}\in{\xiifrak E}$ on the tape of the Turing machine
with processor ${\cal P}$ and we leave it running, then when it halts we will
find the expression $\xiifrak r\in E$ on the tape. If, on the contrary, the
Turing machine $\cal P$ does not halt when we write the expression $\xiifrak
w$, then we would say that $\xiifrak w$ is a paradox in $\cal P$, and we would
indicate this as follows: ${\cal P}\langle{\xiifrak
w}\rangle\hookrightarrow\infty$.

§4.1.7 Definition ${\xiifrak E}^{+}={\xiifrak E}\cup\\{\infty\\}$.

Comment Some computations do not halt, so we need $\infty$ to refer to them.
Note that $\infty\notin{\xiifrak E}$, but $\infty\in{\xiifrak E}^{+}$. So
${\xiifrak E}\subset{\xiifrak E}^{+}$.

§4.1.8 Definition For each Turing machine ${\cal P}\in{\xiifrak T}$ we define
a function $F_{\cal P}:{\xiifrak E}\to{\xiifrak E}^{+}$, this way:

$F_{\cal P}({\xiifrak e})=\cases{{\xiifrak r}&if ${\cal P}\langle{\xiifrak
e}\rangle\hookrightarrow{\xiifrak r}$\cr\infty&if ${\cal P}\langle{\xiifrak
e}\rangle\hookrightarrow\infty$ .\cr}$

Comment If $\forall{\xiifrak e}\in{\xiifrak E},F_{\cal P}({\xiifrak
e})=F_{\cal Q}({\xiifrak e})$, then we say that Turing machines $\cal P$ and
$\cal Q$ are behaviorally equivalent, ${\cal P}\equiv_{F}{\cal Q}$, or that
$\cal P$ and $\cal Q$ implement the same function.

§4.1.9 Definition We say that a function is computable if there is a Turing
machine that implements the function.

§4.1.10 Lemma For each Turing machine we can define a unique finite string of
symbols, that is, $\exists{\xiifrak c}:{\xiifrak T}\to{\xiifrak E}$ such that
${\cal P}={\cal Q}\;\Leftrightarrow\;{\xiifrak c}({\cal P})={\xiifrak c}({\cal
Q})$.

Proof Proved by Turing (1936), §5. Turing machines are defined by their
processors, which are finite state automata. And every finite state automaton
is defined by the table that describes its transition function $\cal T$ in
full, which is a finite table of expressions referring to internal states,
input symbols, and output symbols. A table can be converted to a string just
using an additional symbol for the end of line, and another symbol for the end
of cell. To assure uniqueness, we have to impose some order on the lines and
on the cells. $\diamond$

Comment ${\xiifrak c}({\cal P})\in{\xiifrak E}$ is the string of symbols that
represents the Turing machine ${\cal P}\in{\xiifrak T}$.

§4.1.11 Notation We will refer to ${\xiifrak p}={\xiifrak c}({\cal P})$ as a
program, and to the set of programs as ${\xiifrak P}$. The set of programs is
a proper subset of the set of expressions, ${\xiifrak P}\subset{\xiifrak E}$.

§4.1.12 Definition The program isomorphism is the natural isomorphism that
relates each Turing machine ${\cal P}\in{\xiifrak T}$ with the expression
describing it, ${\xiifrak c}({\cal P})={\xiifrak p}\in{\xiifrak P}$. That is,
${\xiifrak T}\Leftrightarrow{\xiifrak P}:{\cal P}\leftrightarrow{\xiifrak
c}({\cal P})$.

Comment Now, ${\xiifrak T}\cong{\xiifrak P}\subset{\xiifrak E}$.

§4.1.13 Lemma The set of Turing machines is countable, that is, $|{\xiifrak
T}|=|{\xiibb N}|={\aleph}_{0}$.

Proof Proved by Turing (1936), §5. Using the program isomorphism, see §4.1.12,
we order the Turing machines according to its corresponding program ${\xiifrak
p}={\xiifrak c}({\cal P})$. We can order the programs, because they are finite
strings of symbols, for example first by length, and then those of a given
length by some kind of alphabetical order. Once ordered, we can assign a
natural number to each one. $\diamond$

§4.1.14 Theorem All computing sets are countable, that is, $|{\xiifrak
T}|=|{\xiifrak E}|={\aleph}_{0}$.

Proof By Lemmas §4.1.5 and §4.1.13. $\diamond$

Comment All computing is about countable sets. Computing is counting.

§4.2 Turing Completeness

§4.2.1 Theorem There is a Turing machine, called universal Turing machine,
$\cal U$, that can compute anything that any Turing machine can compute. That
is:

$\exists\,{\cal U}\in{\xiifrak T}\mid\forall{\cal P}\in{\xiifrak
T},\forall{\xiifrak d}\in{\xiifrak E},\quad{\cal U}\langle{\xiifrak c({\cal
P})\;d}\rangle={\cal P}\langle{\xiifrak d}\rangle.$

Proof Proved by Turing (1936), §6 and §7. $\diamond$

Comment The equality means that if ${\cal P}\langle{\xiifrak
d}\rangle\hookrightarrow{\xiifrak r}$ then ${\cal U}\langle{\xiifrak c({\cal
P})\;d}\rangle\hookrightarrow{\xiifrak r}$, and the converse, and also that if
${\cal P}\langle{\xiifrak d}\rangle\hookrightarrow\infty$ then ${\cal
U}\langle{\xiifrak c({\cal P})\;d}\rangle\hookrightarrow\infty$, and the
converse. That is, ${\cal U}\langle{\xiifrak c({\cal
P})}\rangle\equiv_{F}{\cal P}$. To complete the definition, if ${\xiifrak
e}\notin{\xiifrak P}$, then ${\cal U}\langle{\xiifrak
e\,d}\rangle\hookrightarrow{\xiifrak e\,d}$.

§4.2.2 Notation We will refer to the set of universal Turing machines as
$\xiifrak U$.

Comment The set of universal Turing machines is a proper subset of the set of
Turing machines, ${\xiifrak U}\subset{\xiifrak T}$.

§4.2.3 Lemma For each universal Turing machine ${\cal U}$ there is a universal
program ${\xiifrak u}$.

Proof Universal Turing machines are Turing machines, and ${\xiifrak
u}={\xiifrak c}({\cal U})$. Then, by the program isomorphism, see §4.1.12,
${\xiifrak u}={\cal U}$. $\diamond$

Comment Given ${\xiifrak u}={\xiifrak c}({\cal U})$ and ${\xiifrak
p}={\xiifrak c}({\cal P})$, then ${\cal U}\langle{\xiifrak p\,d}\rangle={\cal
P}\langle{\xiifrak d}\rangle$ and ${\cal U}\langle{\xiifrak
u\,p\,d}\rangle={\cal U}\langle{\xiifrak p\,d}\rangle$, so $\xiifrak u$ is the
identity for programs, and ${\cal U}\langle{\xiifrak u\,u\,p\,d}\rangle={\cal
U}\langle{\xiifrak u\,p\,d}\rangle={\cal U}\langle{\xiifrak p\,d}\rangle={\cal
P}\langle{\xiifrak d}\rangle$.

§4.2.4 Definition The terminating condition $P_{\sigma}:{\xiifrak T}\to{\xiibb
B}$ is:

$P_{\sigma}({\cal P})=\cases{\bot&if $\exists\,{\xiifrak w}\in{\xiifrak
E},\;{\cal P}\langle{\xiifrak w}\rangle\hookrightarrow\infty$\cr\top&otherwise
.\cr}$

Comment A terminating Turing machine always halts. There are not paradoxes in
a terminating Turing machine. While Turing machines implement partial
functions, ${\xiifrak E}\to{\xiifrak E}^{+}$, see §4.1.8, terminating Turing
machines implement total functions, ${\xiifrak E}\to{\xiifrak E}$.

§4.2.5 Definition The terminating problem is $\sigma=p?P_{\sigma}(p)$. The
non-terminating problem is $\bar{\sigma}=p?\,\neg P_{\sigma}(p)$.

Comment The terminating problem follows from the condition isomorphism of
problems, see §3.1.7, applied to the terminating condition $P_{\sigma}$. The
non-terminating problem is derived from the terminating one by negation, see
§3.1.10.

Comment The set of terminating Turing machines is $\Sigma_{\sigma}$, and the
set of non-terminating Turing machines is $\Sigma_{\bar{\sigma}}$.

Proposition $\Sigma_{\sigma}$ and $\Sigma_{\bar{\sigma}}$ are a partition of
${\xiifrak T}$, because $\Sigma_{\sigma}\cap\Sigma_{\bar{\sigma}}=\emptyset$
and $\Sigma_{\sigma}\cup\Sigma_{\bar{\sigma}}={\xiifrak T}$.

§4.2.6 Definition We will call ${\xiifrak a}={\xiifrak c}({\cal
P}_{\\!\sigma})\in{\xiifrak E}$, where ${\cal
P}_{\\!\sigma}\in\Sigma_{\sigma}$, an algorithm.

Comment $\forall{\xiifrak d},\,{\cal P_{\\!\sigma}}\langle{\xiifrak
d}\rangle\hookrightarrow{\xiifrak
r}\neq\infty\;\Leftrightarrow\;\forall{\xiifrak d},\,{\cal U}\langle{\xiifrak
a\;d}\rangle\hookrightarrow{\xiifrak r}\neq\infty$.

Comment An algorithm is the expression of a computation that always halts.

Notation We will refer to the set of algorithms as ${\xiifrak A}$.

Comment ${\xiifrak A}\subset{\xiifrak P}\subset{\xiifrak E}$.

§4.2.7 Lemma Universal Turing machines are non-terminating, that is,
${\xiifrak U}\subset\Sigma_{\bar{\sigma}}\subset{\xiifrak T}$.

Proof Because there are paradoxes in some Turing machines. For example, for
Turing machine $\cal W$, that has not any $h$ (halt) in its transition table,
every expression is a paradox. That is, $\exists{\cal P}\in{\xiifrak
T},\exists{\xiifrak w}\in{\xiifrak E},\;{\cal P}\langle{\xiifrak
w}\rangle\hookrightarrow\infty\;\Rightarrow\;\forall{\cal U}\in{\xiifrak
U},\;{\cal U}\langle{\xiifrak c({\cal P})\;w}\rangle\hookrightarrow\infty$.
$\diamond$

Comment If expression ${\xiifrak w}$ is a paradox in $\cal P\\!$, then
expression ${\xiifrak c({\cal P})\;w}$ is a paradox in ${\cal U}$. Then,
${\cal U}\in\Sigma_{\bar{\sigma}}$.

§4.2.8 Definition A computing device is Turing complete if it can compute
whatever any Turing machine can compute. We will call every Turing complete
device a universal computer.

Comment The prototype of universal computer is a universal Turing machine,
$\cal U$.

Comment The Turing machine, as it was presented by Turing (1936), models the
calculations done by a person. This means that we can compute whatever any
Turing machine can compute provided we have enough time and memory, and
therefore we are Turing complete provided we have enough time and memory.

§4.2.9 Theorem All universal computers are equivalent.

Proof Gödel and Herbrand recursiveness, Church $\lambda$-definability, and
Turing computability are equivalent, because Kleene (1936) showed that every
recursive function is $\lambda$-definable, and the converse, and then Turing
(1937) showed that every $\lambda$-definable function is computable, and that
every computable function is recursive. $\diamond$

Comment A universal Turing machine is equivalent to a $\lambda$-calculus
interpreter, where a $\lambda$-calculus interpreter is a device that can
perform any $\lambda$-calculus reduction. A universal Turing machine is
equivalent to a mathematician calculating formally, and without errors, any
recursive function.

Comment The universal Turing machine, the $\lambda$-calculus interpreter, and
the mathematician, who is a person, are equal in computing power. And all of
them are Turing complete.

§4.2.10 Proviso Whenever we apply a general statement to a finite universal
computing device, we should add a cautious ‘provided it has enough time and
memory’.

Comment Although the finite universal computer can perform each and every step
of the computation exactly the same as the unrestricted universal computer,
the finite universal computer could meet some limitations of time or memory
that would prevent it to complete the computation. In that case, the same
finite universal computer, provided with some additional time and some more
memory, would perform some more computing steps exactly the same as the
unrestricted universal computer. This extension procedure can be repeated as
desired to close the gap between the finite and the unrestricted universal
computer.

Comment We will understand that the proviso ‘provided it has enough time and
memory’ is implicitly stated whenever we refer to a finite universal computing
device.

§4.2.11 Convention Because all universal computers are equivalent, we can use
any of them, let us call the one used $\cal U$, and then drop every $\cal U$
from the formulas, and just examine expressions, that is, elements in
${\xiifrak E}$. In case we need to note a non-halting computation, we will use
$\infty$.

Comment Using the convention is as if we were always looking inside the tape
of ${\cal U}$. Given a universal computer, $\cal U$, computing is about
expressions manipulating expressions.

Example Formula ${\cal U}\langle{\xiifrak c({\cal P})\
d}\rangle\hookrightarrow{\xiifrak r}$ is reduced to $\langle{\xiifrak c({\cal
P})\ d}\rangle\hookrightarrow{\xiifrak r}$, and even to $\langle{\xiifrak p\
d}\rangle\hookrightarrow{\xiifrak r}$, using the rewriting rule: $\forall{\cal
P}\in{\xiifrak T},\;{\xiifrak c}({\cal P})={\xiifrak p}$. If the universal
computer is a $\lambda$-calculus interpreter, then this is usually written as
the $\beta$-reduction $({\xiifrak p}\ {\xiifrak d})\to{\xiifrak r}$, where the
left hand side is a $\lambda$-application, and ${\xiifrak p}$ is defined by
some $\lambda$-abstraction.

§4.2.12 Definition For each program ${\xiifrak p}\in{\xiifrak P}$ we define a
function ${\xiifrak F}_{\xiifrak p}:{\xiifrak E}\to{\xiifrak E}^{+}$, this
way:

${\xiifrak F}_{\xiifrak p}({\xiifrak e})=\cases{{\xiifrak r}&if
$\langle{\xiifrak p\,e}\rangle\hookrightarrow{\xiifrak r}$\cr\infty&if
$\langle{\xiifrak p\,e}\rangle\hookrightarrow\infty$ .\cr}$

Comment If $\forall{\xiifrak e}\in{\xiifrak E}$, ${\xiifrak F}_{\xiifrak
p}({\xiifrak e})={\xiifrak F}_{\xiifrak q}({\xiifrak e})$, then we say that
programs $\xiifrak p$ and $\xiifrak q$ are behaviorally equivalent, ${\xiifrak
p}\equiv_{\xiifrak F}{\xiifrak q}$, or that $\xiifrak p$ and $\xiifrak q$
implement the same function.

§4.2.13 Theorem $\forall{\cal P}\in{\xiifrak T}$, $F_{\cal P}={\xiifrak
F}_{\xiifrak p}$, where ${\xiifrak p}={\xiifrak c}({\cal P})$.

Proof $\forall{\xiifrak d}\in{\xiifrak E}$, $\forall{\cal P}\in{\xiifrak T}$,
${\xiifrak F}_{\xiifrak p}({\xiifrak d})=F_{\cal P}({\xiifrak d})$, see
§4.1.8, because ${\cal U}\langle{\xiifrak c({\cal P})\ d}\rangle={\cal
P}\langle{\xiifrak d}\rangle$, by Theorem §4.2.1, and therefore $F_{\cal
P}={\xiifrak F}_{\xiifrak p}$ when the universal computer is a universal
Turing machine, $\cal U$. Theorem §4.2.9 extends it to every universal
computer. $\diamond$

Comment $\cal P$ and $\xiifrak p$ implement the same function.

Comment This theorem is a consequence of the program isomorphism, see §4.1.12.
In other words, ${\xiifrak T}\cong{\xiifrak P}$ implies that
$\mathord{\equiv_{F}}\leftrightarrow\mathord{\equiv_{\xiifrak F}}$, so ${\cal
P}\equiv_{F}{\cal Q}\;\Leftrightarrow\;{\xiifrak p}\equiv_{\xiifrak
F}{\xiifrak q}$.

Corollary $F_{\cal U}={\xiifrak F}_{\xiifrak u}$, where ${\xiifrak
u}={\xiifrak c}({\cal U})$.

§4.3 Turing’s Thesis

§4.3.1 Thesis What is effectively calculable is computable.

Comment This is Church’s thesis, or rather Turing’s thesis, as it was
expressed by Gandy (1980). There, ‘something is effectively calculable’ if its
results can be found by some purely mechanical process, see §3.1.5, and
‘computable’ means that the same results will be found by some Turing machine.
Then, ${}^{*}{\xiibb F}\subseteq{\xiifrak T}$.

Comment ‘What is computable is effectively calculable’, or ${\xiifrak
T}\subseteq{}^{*}{\xiibb F}$, is the converse of Turing’s thesis. And it is
obvious that if a Turing machine can compute a function, then the function is
effectively calculable, see §3.1.5, by a Turing machine. Therefore,
${}^{*}{\xiibb F}={\xiifrak T}$, and $|^{*}{\xiibb F}|=\aleph_{0}$, by
§4.1.13.

§4.3.2 Remark An effectively calculable function is not an input to output
mapping; it is a process to calculate the output from the input.

Example To multiply a number expressed in binary by two we can append a ‘0’ to
it, which is an effectively calculable function that we will call app0. But
the complete memoization of the same function, which we will call memoby2, is
not effectively calculable because it would require an infinite quantity of
memory. And therefore, $\hbox{\xiiit app0}\neq\hbox{\xiiit memoby2}$.

§4.3.3 Notation We will call every universe where the Turing’s thesis is true
a Turing universe. When we want to note that something is true in a Turing
universe, we will use an asterisk, so
$A\buildrel\scriptscriptstyle\ast\over{=}B$ means that $A=B$ if the Turing’s
thesis stands.

Examples ${}^{*}{\xiibb F}\buildrel\scriptscriptstyle\ast\over{=}{\xiifrak T}$
and $|^{*}{\xiibb F}|\buildrel\scriptscriptstyle\ast\over{=}{\aleph}_{0}$.

Comment The Turing’s thesis affirms that this is a Turing universe. In any
Turing universe the Turing’s thesis is a law of nature, as it was defended by
Post (1936), last paragraph. Then a Turing universe can also be called a Post
universe.

Comment While the Turing’s thesis is true, you can ignore the asterisks.

§4.3.4 Theorem Universal computers are* the most capable computing devices.

Proof If Turing’s thesis stands, see §4.3.1, then anything that any mechanism
can effectively calculate can be computed by some Turing machine, and
therefore, by Theorem §4.2.1, it can be computed by any universal Turing
machine, and finally, by Theorem §4.2.9, it can be computed by any universal
computer. $\diamond$

§4.3.5 Lemma There are definable functions that no Turing machine can compute.

Proof You can use a diagonal argument, or work from other theorems that use
the diagonal argument. For example, the set of Turing machines is countable,
see §4.1.13, $|{\xiifrak T}|=|{\xiibb N}|={\aleph}_{0}$, while the possible
number of predicates on natural numbers, that is, the number of functions
${\xiibb N}\to{\xiibb B}$, is $2^{|{\xiibb N}|}=2^{{\aleph}_{0}}$, which is
not countable, $|{\xiifrak T}|=|{\xiibb
N}|={\aleph}_{0}<2^{{\aleph}_{0}}=2^{|{\xiibb N}|}$. This uses Cantor’s
theorem, $|S|<|2^{S}|$, with its diagonal argument. So there are not enough
Turing machines to compute every definable function. $\diamond$

Corollary Universal computers cannot compute every definable function.

Comment If the Turing’s thesis stands, see §4.3.1, then it follows that there
are definable functions that are not effectively calculable, see §3.1.5.

Comment There are* more mappings than processes.

§4.3.6 Definition The identity Turing machine, $\cal I$, just halts.

Comment It does nearly nothing. But, wait!

§4.3.7 Lemma $\forall{\xiifrak x}\in{\xiifrak E},\;{\cal I}\langle{\xiifrak
x}\rangle\hookrightarrow{\xiifrak x}$, where $\cal I$ is the identity Turing
machine.

Proof Whatever expression ${\xiifrak x}\in{\xiifrak E}$ is written on the tape
of $\cal I$, that very same expression ${\xiifrak x}$ is written when $\cal I$
halts, because halting is all what $\cal I$ does. $\diamond$

Comment $\cal I$ does not touch the expression.

§4.3.8 Lemma The identity Turing machine is terminating, that is, ${\cal
I}\in\Sigma_{\sigma}$.

Proof The identity Turing machine, which just halts, is terminating, see
§4.2.5, because it always halts; it only halts. $\diamond$

Comment $\cal I$ behaves, because sometimes ‘you can look, but you better not
touch’.

§4.3.9 Lemma The identity Turing machine $\cal I:{\xiifrak E}\to{\xiifrak E}$
is* the identity function $i:{\xiibb S}\to{\xiibb S}$ such that $\forall
x\in{\xiibb S}$, $i(x)=x$, that is, ${\cal
I}\buildrel\scriptscriptstyle\ast\over{=}i$.

Proof The identity function $i$ is an effectively calculable function, see
§3.1.5. Therefore, if the Turing’s thesis stands, see §4.3.1, then there is a
Turing machine ${\cal J}$ such that $\forall{\xiifrak x}\in{\xiifrak
E},\;{\cal J}\langle{\xiifrak x}\rangle\hookrightarrow{\xiifrak x}$. By Lemma
§4.3.7, that Turing machine ${\cal J}$ is the identity Turing machine ${\cal
I}$. $\diamond$

Comment If ${\xiifrak i}={\xiifrak c}({\cal I})$, then ${\cal
U}\langle{\xiifrak i\,p\,d}\rangle={\cal I}\langle{\xiifrak
p\,d}\rangle\hookrightarrow{\xiifrak p\,d}$, and ${\cal U}\langle{\xiifrak
u\,p\,d}\rangle={\cal U}\langle{\xiifrak p\,d}\rangle={\cal P}\langle{\xiifrak
d}\rangle\hookrightarrow{\xiifrak r}$, or $\infty$, see §4.2.3. Then $\xiifrak
i$ is the literal identity for expressions, or quotation, and $\xiifrak u$ is
the functional identity for programs, or evaluation. Both are computable, but
${\cal I}\in\Sigma_{\sigma}$ and ${\cal U}\in\Sigma_{\bar{\sigma}}$, see
§4.2.7.

§4.3.10 Theorem Everything is* an expression, that is, ${\xiifrak
E}\buildrel\scriptscriptstyle\ast\over{=}{\xiibb S}$.

Proof ${\xiibb S}$ is the set of everything, see §3.2.1. In computing, there
are only computing devices, $\xiifrak T$, and expressions, $\xiifrak E$, see
§4.1.4. But then, by the program isomorphism, see §4.1.12, computing devices
are expressions, ${\xiifrak T}\subset{\xiifrak E}$. Therefore, in computing
everything is an expression. And now, if the Turing’s thesis stands, see
§4.3.1, then Lemma §4.3.9 also stands, so $\forall x\in{\xiibb
S},\,x=i(x)\buildrel\scriptscriptstyle\ast\over{=}{\cal I}\langle{\xiifrak\mit
x}\rangle\hookrightarrow x\in{\xiifrak E}$. The converse, $\forall{\xiifrak
x}\in{\xiifrak E},\,{\xiifrak x}\hookleftarrow{\cal I}\langle{\xiifrak
x}\rangle=i({\xiifrak x})={\xiifrak x}\in{\xiibb S}$, holds irrespective of
Turing’s thesis. Therefore, ${\xiibb
S}\buildrel\scriptscriptstyle\ast\over{=}{\xiifrak E}$. $\diamond$

Comment We will write $\xiifrak x$ to indicate a computing point of view of
$x$, but $\forall x,\,x\buildrel\scriptscriptstyle\ast\over{=}{\xiifrak x}$.
For example, $i\buildrel\scriptscriptstyle\ast\over{=}{\xiifrak i}$.

§4.3.11 Lemma The set of solutions ${\xiibb S}$ is* countable, that is,
$|{\xiibb S}|\buildrel\scriptscriptstyle\ast\over{=}\aleph_{0}$.

Proof ${\xiibb S}\buildrel\scriptscriptstyle\ast\over{=}{\xiifrak E}$, by
§4.3.10, and $|{\xiifrak E}|=|{\xiibb N}|={\aleph}_{0}$, by §4.1.5, therefore
$|{\xiibb S}|\buildrel\scriptscriptstyle\ast\over{=}|{\xiifrak
E}|={\aleph}_{0}$. $\diamond$

Comment We will refer to the set of solutions in a Turing universe as ${\xiibb
S}^{*}$. So we can also write this lemma as $|{\xiibb S}^{*}|={\aleph}_{0}$.

§4.3.12 Theorem Resolving is* computing, that is, ${\xiifrak
T}\buildrel\scriptscriptstyle\ast\over{=}{\xiibb R}$.

Proof From Theorem §4.3.10, everything is* an expression, and taking
transitions and not states, it follows that whatever transforms expressions in
computing theory, that is, a Turing machine ${\cal P}$, or its equivalent
program ${\xiifrak p}$, or a $\lambda$-function of the $\lambda$-calculus, is*
equivalent to whatever transforms sets in set theory, that is, an effectively
calculable function, and it is* also equivalent to whatever transforms
problems in problem theory, that is, a resolution $\Re$. Therefore, resolving
is* computing, ${\xiibb R}\buildrel\scriptscriptstyle\ast\over{=}{\xiifrak
T}$. $\diamond$

Comment ${}^{*}\\!f\buildrel\scriptscriptstyle\ast\over{\equiv}{\cal
P}\equiv{\xiifrak p}\buildrel\scriptscriptstyle\ast\over{\equiv}{\Re}$, and
${}^{*}{\xiibb F}\buildrel\scriptscriptstyle\ast\over{=}{\xiifrak
T}\buildrel\scriptscriptstyle\ast\over{=}{\xiibb R}$.

Comment We can define functions that are not effectively calculable, see
§4.3.5. Those functions that cannot effectively calculate, cannot therefore
transform, and they are, in this sense, useless; we can define them, but we
cannot use them.

Corollary Metasolutions are* effectively calculable functions, that is,
$\Pi{\xiibb S}\buildrel\scriptscriptstyle\ast\over{=}{}^{*}{\xiibb F}$.

Proof Because ${\xiibb R}=\Pi{\xiibb S}$, see §3.5.8, so $\Pi{\xiibb
S}={\xiibb R}\buildrel\scriptscriptstyle\ast\over{=}{}^{*}{\xiibb F}$.
$\diamond$

§4.3.13 Lemma The set of resolutions ${\xiibb R}$ is* countable, that is,
$|{\xiibb R}|\buildrel\scriptscriptstyle\ast\over{=}\aleph_{0}$.

Proof ${\xiibb R}\buildrel\scriptscriptstyle\ast\over{=}{\xiifrak T}$, by
§4.3.12, and $|{\xiifrak T}|=|{\xiibb N}|={\aleph}_{0}$, by §4.1.13, therefore
$|{\xiibb R}|\buildrel\scriptscriptstyle\ast\over{=}|{\xiifrak
T}|={\aleph}_{0}$. $\diamond$

Comment We will refer to the set of resolutions in a Turing universe as
${\xiibb R}^{*}$. So we can also write this lemma as $|{\xiibb
R}^{*}|={\aleph}_{0}$.

§4.3.14 Lemma Predicate $P_{\delta_{s}}$, where $P_{\delta_{s}}\\!(x)=[x=s]$,
is* effectively calculable.

Proof Both $s$ and $x$ are* expressions, by §4.3.10, so both are finite
strings of symbols, $s=s_{1}s_{2}\dots s_{n}$, and $x=x_{1}x_{2}\dots x_{m}$.
Then we can define a Turing machine with $n+2$ states, that starts in state
$1$, and that when some string $x$ is written on its tape, it scans the string
$x$, symbol by symbol, from the leftest one, this way: 1) in state $i$, with
$1\leq i\leq n$, if the read symbol is $s_{i}$, then it writes a blank, goes
to state $i+1$, and moves to the right, but if the read symbol is not $s_{i}$,
then it writes a blank, goes to state $0$, and moves to the right; 2) in state
$n+1$, if the read symbol is blank, then it writes a $\top$, goes to state
$0$, and halts, but if the read symbol is not blank, then it writes a blank,
goes to state $0$, and moves to the right; 3) in state $0$, if the read symbol
is not blank, then it writes a blank, goes to state $0$, and moves to the
right, but if the read symbol is blank, then it writes a $\bot$, goes to state
$0$, and halts. This Turing machine implements $P_{\delta_{s}}$, and therefore
$P_{\delta_{s}}$ is computable. $\diamond$

Corollary Problem $\delta_{s}=x?[x=s]$ is* expressible.

Proof Because problem $\delta_{s}$ condition $P_{\delta_{s}}$ is* effectively
calculable, see §3.1.6. $\diamond$

Comment Problem $\delta_{s}$ is used in the proof of Theorem §3.2.1.

Corollary The only solution to problem $\delta_{s}$ is $s$, so
$\Sigma_{\delta_{s}}=\\{s\\}\in{\xiibb S}^{1}$.

Proof Because $\Sigma_{\delta_{s}}=\\{\,x\mid
P_{\delta_{s}}\\!(x)\,\\}=\\{\,x\mid[x=s]\,\\}=\\{s\\}$. $\diamond$

§4.3.15 Lemma The set of problems ${\xiibb P}$ is* countable, that is,
$|{\xiibb P}|\buildrel\scriptscriptstyle\ast\over{=}\aleph_{0}$.

Comment We will refer to the set of problems in a Turing universe as ${\xiibb
P}^{*}$. So we can also write this lemma as $|{\xiibb P}^{*}|={\aleph}_{0}$.
If the condition of a problem is computable, then the problem is in ${\xiibb
P}^{*}$; $\delta_{s}\in{\xiibb P}^{*}$, for example.

Proof Problem $\delta_{s}$ is* expressible, see §4.3.14. Then,
$\delta_{{\xiibb S}^{*}}=\\{\,\delta_{s}\mid s\in{\xiibb
S}^{*}\,\\}\subseteq{\xiibb P}^{*}$ because each $\delta_{s}\in{\xiibb
P}^{*}$, and $|\delta_{{\xiibb S}^{*}}|=|{\xiibb S}^{*}|$ because there is a
bijection $\delta_{{\xiibb S}^{*}}\Leftrightarrow{\xiibb
S}^{*}:\delta_{s}\leftrightarrow s$. Also, by Theorem §4.3.10, ${\xiibb
P}^{*}\subseteq{\xiifrak E}$. Therefore, $\delta_{{\xiibb
S}^{*}}\subseteq{\xiibb P}^{*}\subseteq{\xiifrak E}$, and $|\delta_{{\xiibb
S}^{*}}|=|{\xiibb S}^{*}|={\aleph}_{0}=|{\xiifrak E}|$, and then, by the
Cantor-Bernstein-Schröder theorem, $|{\xiibb P}^{*}|=\aleph_{0}$. $\diamond$

Comment The Cantor-Bernstein-Schröder theorem is Theorem B of §2, page 484, in
Cantor (1895). We have really used the equivalent Theorem C, in the same page.

§4.3.16 Theorem All problem sets are* countable, that is, $|{\xiibb
S}^{*}|=|{\xiibb P}^{*}|=|{\xiibb R}^{*}|=\aleph_{0}$.

Proof By Lemmas §4.3.11, §4.3.15, and §4.3.13. $\diamond$

§4.4 Full Resolution Machine

§4.4.1 Definition A full resolution machine is a device that can execute any
resolution.

§4.4.2 Theorem A full resolution machine is* a Turing complete device.

Proof By Theorem §4.3.12, resolving is* computing,
${\Re}\buildrel\scriptscriptstyle\ast\over{\equiv}{\cal P}$. This means that
to achieve the maximum resolving power is* to achieve the maximum computing
power, which is* the computing power of a universal computer, by Theorem
§4.3.4. Therefore, in a Turing universe a full resolution machine has to be
Turing complete. $\diamond$

Comment To execute any resolution ${\Re}:{\xiibb P}\to 2^{\xiibb S}$, the full
resolution machine has to calculate functions that can take functions and that
can return functions without limitations, as $2^{2^{\xiibb S}\to 2^{\xiibb
S}}\to 2^{2^{\xiibb S}\to 2^{\xiibb S}}$ for meta-analogies, see §3.6.9. Then
a full resolution machine has to execute every possible function, and
therefore, in a Turing universe, it has to execute every computable function,
and then it has to be a $\lambda$-calculus interpreter, or an equivalent
computing device, for example $\cal U$.

Comment This means that problem resolving is* equal to computing, and then
full problem resolving is* equal to universal computing.

Corollary A full resolution machine* is a universal computer.

Proof Because a full resolution machine is* a universal computer. $\diamond$

Comment Now we will state two equivalences between computing theory and
problem theory concepts that are true in any Turing universe, and that are
needed to show the limitations of full resolution machines.

§4.4.3 Definition A set is recursively enumerable if there is a Turing machine
that generates all of its members, and then halts.

Comment If the set is infinite, the Turing machine will keep generating its
members forever.

Definition A set is computable if it is recursively enumerable.

§4.4.4 Theorem Resolvable in problem theory is* equivalent to recursively
enumerable in computing theory, that is,

$\hbox{Resolvable}\buildrel\scriptscriptstyle\ast\over{=}\hbox{Recursively
Enumerable}\;.$

Proof To see that a problem is resolvable if, and only if, the set of its
solutions is recursively enumerable, just compare the definition of resolvable
problem, in §3.5.4, with the definition of recursively enumerable set, in
§4.4.3. The only remaining gap is to equate the valid resolution $\Re$ of the
resolvable problem to the Turing machine of the recursively enumerable set, a
gap that we can bridge with the help of Theorem §4.3.12. Finally see that, by
the set isomorphism, see §3.2.9, we can refer interchangeably to the problem
$\pi$ or to the set of its solutions $\Sigma_{\pi}$. Then we can say that a
problem is recursively enumerable, or that a set is resolvable. $\diamond$

§4.4.5 Definition A set is recursive if its characteristic function can be
computed by a Turing machine that always halts.

§4.4.6 Theorem Expressible in problem theory is* equivalent to recursive in
computing theory, that is,

$\hbox{Expressible}\buildrel\scriptscriptstyle\ast\over{=}\hbox{Recursive}\;.$

Proof The condition of a problem, $P_{\pi}$, is the characteristic function of
the set of its solutions, because $\Sigma_{\pi}=\\{\,s\mid P_{\pi}(s)\,\\}$,
see §3.2.2. Then, if the set of all the solutions to a problem is a recursive
set, see §4.4.5, then the condition $P_{\pi}$ can be computed by a Turing
machine that always halts. So the condition $P_{\pi}$ is an effectively
calculable function, and therefore the problem is expressible, see §3.1.6. If
Turing’s thesis, §4.3.1, is true, then the converse is also true; just go
backwards from expressible to recursive. Finally, by the set isomorphism, see
§3.2.9, we can refer interchangeably to the problem $\pi$ or to the set of its
solutions $\Sigma_{\pi}$. Then, we can say that a problem is recursive, or
that a set is expressible. $\diamond$

§4.4.7 Lemma The limitations of full resolution machines are* the limitations
of universal computers.

Proof Because a full resolution machine is* a universal computer, see §4.4.2.
$\diamond$

Comment Even if universal computers are the most capable computers, they
cannot compute everything, see §4.3.5. Now we will present three limits
related to problems.

§4.4.8 Lemma A full resolution machine can* execute any resolution, but it
cannot* express some problems.

Proof There is a recursively enumerable set that is not recursive; this is the
last theorem in Post (1944) §1. Translating, by Theorems §4.4.4 and §4.4.6, to
problem theory: there is* a resolvable problem that is* not expressible.
$\diamond$

Comment This is the problem limit of full resolution machines*.

Comment That last theorem in Post (1944) §1, page 291, is an abstract form of
Gödel’s incompleteness theorem, see Post (1944) §2.

§4.4.9 Lemma A full resolution machine can* execute any resolution, but it
cannot* resolve some problems.

Proof Let us call $\kappa$ some problem that is resolvable but not
expressible, see §4.4.8. This means that
$\exists\Re\mid\Re(\kappa)=\Sigma_{\kappa}$, but $\mathord{\\!\not\,}\exists
P_{\kappa}\mid P_{\kappa}(x)=[x\in\Sigma_{\kappa}]$. Note that
$|\Sigma_{\kappa}|\geq\aleph_{0}$, because otherwise $\exists P_{\kappa}$.
Then its metaproblem $\Pi\kappa$ is solvable but not resolvable. $\Pi\kappa$
is solvable because $\kappa$ is resolvable, see §3.5.12, or, easier, because
$\Re$ is a solution to $\Pi\kappa$. For $\Pi\kappa$ to be resolvable there
should be a resolution that would find ‘all the solutions of $\Pi\kappa$’,
that is, ‘all the valid resolutions for $\kappa$’. But, whenever a possible
valid resolution for $\kappa$, let us call it $\Re^{\prime}$, generates a
value not yet generated by $\Re$, let us call it $z$, we cannot decide whether
$z\in\Sigma_{\kappa}$ and it will be eventually generated by $\Re$, or if
$z\notin\Sigma_{\kappa}$ and it will never be generated by $\Re$; remember
that $\kappa$ is not expressible, $\mathord{\\!\not\,}\exists P_{\kappa}$.
And, not being able to decide on $z$, we cannot decide whether $\Re^{\prime}$
is a valid resolution for $\kappa$ or not. $\diamond$

Comment This is the resolution limit of full resolution machines*.

Comment Problem $\kappa$ is named after the complete set $K$ of Post (1944),
§3.

§4.4.10 Lemma A full resolution machine can execute any resolution, but it
cannot solve some problems.

Proof Simply because some problems have not any solution,
$\Sigma_{\pi}=\\{\\}=\emptyset$. $\diamond$

Comment This is the solution limit of full resolution machines, which also
applies to full resolution machines*.

Comment An unsolvable problem can be resolved by showing that it has not any
solution. For example, the decision problem of the halting problem,
$\Delta\eta$, see §4.5.4 below, was resolved unsolvable by Turing (1936), §8.

§4.4.11 Theorem A full resolution machine* can execute any resolution, but it
cannot express some problems (problem limit), and it cannot resolve some
problems (resolution limit), and it cannot solve some problems (solution
limit).

Proof By Lemmas §4.4.8, §4.4.9, and §4.4.10. $\diamond$

Comment Full resolution machines* have limitations on each of the three main
concepts of the problem theory.

$\hbox{Problem}\,\mathop{\hbox
to87.96683pt{\rightarrowfill}}\limits^{\hbox{$\scriptstyle\hbox{\quad\xiirm
Resolution\quad}$}}\,\\{\,\hbox{Solution}\,\\}$

§4.5 Problem Topology

§4.5.1 Definition The decision problem of a problem $\pi=x?P_{\pi}(x)$,
written $\Delta\pi$, is:

$\Delta\pi={\cal P}?\;[{\cal P}\in\Sigma_{\sigma}]\land[\forall({\xiifrak
x}\buildrel\scriptscriptstyle\ast\over{=}x),\,{\cal P}\langle{\xiifrak
x}\rangle\buildrel\scriptscriptstyle\ast\over{=}P_{\pi}(x)].$

Comment A solution to the decision problem $\Delta\pi$ of some original
problem $\pi$ is a Turing machine $\cal P$ that always halts and that computes
the original problem condition $P_{\pi}$ for any input. Decision problems are
only defined in Turing universes, where ${\xiifrak
x}\buildrel\scriptscriptstyle\ast\over{=}x$ by Theorem §4.3.10.

Comment This definition follows Post (1944), page 287.

§4.5.2 Definition The halting condition $P_{\eta}:{\xiifrak T}\times{\xiifrak
E}\to{\xiibb B}$ is:

$P_{\eta}({\cal P},{\xiifrak d})=\cases{\bot&if ${\cal P}\langle{\xiifrak
d}\rangle\hookrightarrow\infty$\cr\top&otherwise .\cr}$

§4.5.3 Definition The halting problem is $\eta=(p,d)?P_{\eta}(p,d)$.

Comment The halting problem $\eta$ corresponds to the halting condition
$P_{\eta}$ by the condition isomorphism of problems, see §3.1.7.

Comment $P_{\sigma}(p)=\bigwedge_{d\in{\xiifrak E}}P_{\eta}(p,d)$, see §4.2.5,
so $\sigma=\bigwedge_{d\in{\xiifrak E}}\eta$, by §3.1.7 and §3.1.10.

§4.5.4 Definition The decision problem of the halting problem, $\Delta\eta$,
is:

$\Delta\eta={\cal H}?\;[{\cal H}\in\Sigma_{\sigma}]\land[\forall{\cal
P}\in{\xiifrak T},\forall{\xiifrak d}\in{\xiifrak E},\,{\cal
H}\langle{\xiifrak c({\cal P})\ d}\rangle=P_{\eta}({\cal P},{\xiifrak d})].$

§4.5.5 Theorem The decision problem of the halting problem $\Delta\eta$ has
not any solution.

Proof Turing (1936), §8, resolved that $\Delta\eta$ is unsolvable. $\diamond$

Comment There is not any Turing machine that always halts and that compute
$P_{\eta}$ for each possible input. There is not any algorithm ${\xiifrak
a}\in{\xiifrak A}$ that would compute $P_{\eta}({\xiifrak p},{\xiifrak d})$
for every pair $({\xiifrak p},{\xiifrak d})\in{\xiifrak P}\times{\xiifrak E}$.

§4.5.6 Lemma The decision problem $\Delta\pi$ of some problem $\pi$ is
solvable if, and only if, the problem $\pi$ is expressible*, that is,
$\Delta\pi\hbox{ is solvable}\Leftrightarrow\pi\hbox{ is expressible*}$.

Proof From solvable to expressible. That the decision problem $\Delta\pi$ is
solvable, see §4.5.1, means that there is a Turing machine that always halts,
and that computes $P_{\pi}$ for each possible input. Therefore, $P_{\pi}$ is
effectively calculable, see §3.1.5, by a Turing machine, and then the problem
$\pi$ is expressible, see §3.1.6, and then it is also expressible*. Now from
expressible to solvable. If a problem $\pi$ es expressible, then its condition
$P_{\pi}$ is an effectively calculable function, see §3.1.6. Then, if the
Turing’s thesis stands, see §4.3.1, that is, if it is expressible*, then there
is a Turing machine $\cal P$ that can compute $P_{\pi}$ exactly as the
effectively calculable function. $\cal P$ always halts, because $P_{\pi}$ is a
condition, so its result is finite. Therefore, the decision problem
$\Delta\pi$ of the problem has a solution, $\cal P$, and then $\Delta\pi$ is
solvable, see §3.2.14. $\diamond$

Corollary The halting problem $\eta$ is not expressible*.

Proof The decision problem of the halting problem, $\Delta\eta$, is not
solvable, see §4.5.5, and then the halting problem $\eta$ is not expressible*.
$\diamond$

Comment The halting problem $\eta$ is inexpressible*, but solvable. While the
decision problem of the halting problem $\Delta\eta$ is unsolvable, the
halting problem $\eta$ has many solutions.

§4.5.7 Theorem The following equivalences stand:

$\openup-3.0pt\eqalign{\Delta\pi\hbox{ is
solvable}\buildrel\scriptscriptstyle\ast\over{\Leftrightarrow}&\;\pi\hbox{ is
expressible},\cr\Pi\pi\hbox{ is solvable}\Leftrightarrow&\;\pi\hbox{ is
resolvable},\cr\pi\hbox{ is solvable}\Leftrightarrow&\;\pi\hbox{ is
solvable}.\cr}$

Proof The last one is trivial, and the other two equivalences were already
proved by Lemmas §4.5.6 and §3.5.12. $\diamond$

§4.5.8 Definition A problem $\pi$ can be: expressible* ($\cal E$) or not
expressible* ($\overline{\cal E}$), resolvable* ($\cal R$) or not resolvable*
($\overline{\cal R}$), and solvable ($\cal S$) or not solvable
($\overline{\cal S}$).

Comment An expressible problem is* equivalent to a recursive set, by Theorem
§4.4.6, a resolvable problem is* equivalent to a recursively enumerable set,
by Theorem §4.4.4, and an unsolvable problem is equivalent to an empty set.

Comment Then $\cal R$ is the set of computable sets, see §4.4.3.

Comment Not every combination is possible.

§4.5.9 Lemma If a problem is expressible*, then it is resolvable*, that is,
${\cal E}\subset{\cal R}$.

Proof Because every recursive set is recursively enumerable, ${\cal
E}\subseteq{\cal R}$. This is a corollary to the first theorem in Post (1944)
§1. And ${\cal E}\neq{\cal R}$, see the proof of Lemma §4.4.8. To translate
between sets and problems we use Theorems §4.4.4 and §4.4.6. $\diamond$

Comment The first theorem in Post (1944) §1, page 290, states that a set $M$
is recursive if and only if both the set $M$ and its complement $\overline{M}$
are recursively enumerable.

§4.5.10 Lemma If a problem is not solvable, then it is expressible*, that is,
$\overline{\cal S}\subset{\cal E}$.

Proof If a problem $\nu$ is not solvable, $\nu\in\overline{\cal S}$, then
$\Sigma_{\nu}=\\{\\}$, see §3.2.14. So $\nu$ is a contradictory problem, see
§3.1.11, and its condition $P_{\nu}$ is the contradiction $P_{\bar{\tau}}$,
that is, $\forall x,P_{\nu}(x)=P_{\bar{\tau}}(x)=\bot$. So
$P_{\nu}=P_{\bar{\tau}}$ is an effectively calculable function, see §3.1.5,
and therefore $\nu$ is expressible, see §3.1.6, and then expressible*. And
$\overline{\cal S}\neq{\cal E}$, because $(x?[2x=x^{2}])\in{\cal S}\cap{\cal
E}$. $\diamond$

Comment Being expressible*, by Lemma §4.5.9, $\nu$ is also resolvable*:
$\overline{\cal S}\subset{\cal E}\subset{\cal R}$.

§4.5.11 Theorem Regarding expressibility* $\cal E$, resolvability* $\cal R$,
and solvability $\cal S$, the topology of the problem space is:

$\overline{\cal S}\subset{\cal E}\subset{\cal R}\subset{\xiibb P}\,.$

Proof By Lemmas §4.5.9 and §4.5.10. As shown in the table, these lemmas
prevent four of the eight combinations, and the examples show that the other
four do exist.

$\halign{\hfil$#$\hfil& \space\hfil$#$\hfil& \space\hfil$#$\hfil&
\quad#\hfil\cr\cal E&\cal R&\cal S&Example\&Comment\cr\hrule\kern
3.0pt\cr\top&\top&\top&$x? [2x = x^2]$\cr\top&\top&\bot&$x? [2x = x^2] \land[x
> 2]$\cr\top&\bot&\top&None,byLemma~{}{}\leavevmode\S
4.5.9\cr\top&\bot&\bot&None,byLemma~{}{}\leavevmode\S
4.5.9\cr\bot&\top&\top&$\kappa$,see{}\leavevmode\S
4.4.9\cr\bot&\top&\bot&None,byLemma~{}{}\leavevmode\S
4.5.10\cr\bot&\bot&\top&$\Pi\kappa$,see{}\leavevmode\S
4.4.9\cr\bot&\bot&\bot&None,byLemma~{}{}\leavevmode\S
4.5.10\quad{\diamond}\cr}$

Corollary Then, $\\{\,\overline{\cal S},{\cal E}\cap{\cal S},{\cal
R}\cap\overline{\cal E},\overline{\cal R}\,\\}$ is a partition of ${\xiibb
P}$.

Comment See below, in §6.2, that ${\cal
E}\buildrel\scriptscriptstyle\ast\over{=}{\xiibb P}$, and then ${\xiibb
P}^{*}\subset\xiibb P$. Also ${\cal
R}\buildrel\scriptscriptstyle\ast\over{=}2^{\xiibb S}$.

§4.5.12 Definition We say that a problem is finite, if the set of its
solutions is finite. We will refer to the set of finite problems as $\cal F$.
That is, ${\cal F}=\\{\,\pi\mid\,|\Sigma_{\pi}|<\aleph_{0}\,\\}$.

§4.5.13 Lemma The set of finite problems $\cal F$ is a proper subset of the
set of expressible problems $\cal E$. The set of not solvable problems
$\overline{\cal S}$ is a proper subset of the set of finite problems $\cal F$.
That is, $\overline{\cal S}\subset{\cal F}\subset{\cal E}$.

Proof ${\cal F}\subset{\cal E}$ because all finite sets are recursive, but not
the converse. $\overline{\cal S}\subset{\cal F}$ because
$\forall\nu\in\overline{\cal S},\;|\Sigma_{\nu}|=0<\aleph_{0}$, but
$(x?[2x=x^{2}])\in{\cal S}\cap{\cal F}$. $\diamond$

Proposition Including ${\cal F}$, the topology of ${\xiibb P}$ is:
$\overline{\cal S}\subset{\cal F}\subset{\cal E}\subset{\cal R}\subset{\xiibb
P}$.

Corollary The topology $\overline{\cal S}\subset{\cal F}\subset{\cal
E}\subset{\cal R}\subset{\xiibb P}$ partitions the problem space $\xiibb P$
into five non-empty places: $\overline{\cal S}$, ${\cal F}\cap{\cal S}$,
${\cal E}\cap\overline{\cal F}$, ${\cal R}\cap\overline{\cal E}$, and
$\overline{\cal R}$.

§4.5.14 Remark The upper part of this topology is further refined by the so
called Turing degrees of unsolvability, that we will call Turing degrees of
inexpressibility. Turing degree zero, $\xiibf 0$, corresponds to the first
three places, because ${\cal E}={\xiibf 0}$.

Comment Then, $|{\cal E}|=|{\xiibf 0}|=\aleph_{0}$, $|{\cal R}|=\aleph_{0}$,
and $|{\xiibb P}|=2^{\aleph_{0}}>\aleph_{0}$. To complete the cardinalities,
$|\overline{\cal S}|=1$, so $|{\cal S}|=2^{\aleph_{0}}$, and $|{\cal
F}|=\aleph_{0}$.

§4.5.15 Remark Noting ${\cal E}^{p}$ the set of problems defined by a
condition that can be computed in polynomial time, and ${\cal R}^{p}$ the set
of problems that can be resolved in polynomial time, then ${\cal
E}^{p}\subset{\cal E}$ and ${\cal R}^{p}\subset{\cal R}$. The so called ‘P =
NP?’ question asks if ${\cal E}^{p}={\cal R}^{p}$, because ${\xiirm P}={\cal
E}^{p}$ and ${\xiirm NP}={\cal R}^{p}$, and then it should be called the
‘${\cal E}^{p}={\cal R}^{p}?$’ question. See that the general question ‘${\cal
E}={\cal R}?$’ was answered negatively by Lemma §4.5.9, because ${\cal
E}\subset{\cal R}$, and that ${\cal E}^{p}\subseteq{\cal R}^{p}$.

Comment A similar question is ‘${\cal E}^{p}\setminus\\{\emptyset\\}={\cal
S}^{p}?$’, where ${\cal S}^{p}$ is the set of problems that can be solved in
polynomial time, so ${\cal S}^{p}\subset{\cal S}$. The corresponding general
question is also answered negatively, because ${\xiibb P}={\cal
S}\cup\\{\emptyset\\}$, so ${\cal E}\setminus\\{\emptyset\\}\subset{\cal S}$.

§5 Resolvers

§5.1 Semantics and Syntax

§5.1.1 Remark In this Section §5, we will always be inside a Turing universe,
see §4.3.3, and accordingly we will drop every asterisk. Though some results
do not depend on Turing’s thesis, by now the reader should know when it is the
case.

§5.1.2 Definition A resolver is a device that takes problems and returns
solutions.

Comment A resolver executes resolutions.

Comment After Theorem §4.3.12, we can equate a resolution $\Re\in\xiibb R$ to
the computing device that executes the resolution ${\cal P}\in{\xiifrak T}$,
that is, $\Re={\cal P}$.

§5.1.3 Definition We will call the domain of ${\xiibb S}$ semantics. We will
call the domain of ${\xiibb S}\to{\xiibb S}$ syntax.

Comment As $\lambda$-calculus shows, we only need functions to implement any
syntax.

Comment By Theorem §3.2.1, everything is in ${\xiibb S}$, including ${\xiibb
S}\to{\xiibb S}$. But this is both mathematically impossible, by Cantor’s
theorem, and practically not interesting.

Example Using a practical example, if the problem is the survival problem, so
some behaviors keep the resolver alive, and the rest cause the death of the
resolver, then ${\xiibb S}$ is the set of behaviors, and it does not include
anything that is not a behavior, not even predicates on behaviors, nor
functions. Note that the condition of the survival problem, which is satisfied
if the resolver does not die, is a predicate on behaviors.

§5.1.4 Remark In this Section §5, we will assume that ${\xiibb S}$ is not the
set of everything, and, in particular, we will assume that there is not any
function in ${\xiibb S}$. We will focus on the survival problem, and then
assume that ${\xiibb S}$ is the set of behaviors, or finite state automata,
but you can think that ${\xiibb S}={\xiibb N}$, or any other countable set,
see §4.3.11. Then we will build a series of resolvers, from the simplest one
implementing one element of ${\xiibb S}$, to more complex resolvers that have
to implement functions in order to look for resolutions to deal with
metaproblems.

§5.1.5 Definition A problem type, for example ${\xiibb P}_{\Psi}$, is a subset
of the set of problems, that is, ${\xiibb P}_{\Psi}\subseteq{\xiibb P}$. We
will note ${\xiibb S}_{\Psi}$ the set of the solutions to the type of problems
${\xiibb P}_{\Psi}$. That is, $\forall\pi_{\Psi}\in{\xiibb P}_{\Psi}$,
$\Sigma_{\pi_{\Psi}}\subseteq{\xiibb S}_{\Psi}\subseteq{\xiibb S}$.

Comment The survival problem is not a single problem, but a type of problems,
${\xiibb P}_{\Omega}$; each living being faces a different survival problem.
But, in this case as in many others, what it is certain is that the solutions
to any of these problems is of a specific kind. For example, while eating can
be a solution, imagining how to eat is not a solution, even though it can help
us to get something to eat, because it can be a metasolution. Then ${\xiibb
S}_{\Omega}$ is the set of behaviors.

§5.1.6 Remark Metaproblems $\Pi\pi$ are a type of problem, $\Pi{\xiibb
P}={\xiibb P}_{\Pi}$, and its solutions are resolutions, $\Pi{\xiibb
S}={\xiibb S}_{\Pi}={\xiibb R}$, see §3.5.8.

§5.1.7 Lemma If the set of the solutions to some type of problem is finite,
$0<|{\xiibb S}_{\Gamma}|<{\aleph_{0}}$, then each and every problem of that
type is expressible and resolvable.

Proof Because those problems are in $\cal F$, so Lemma §4.5.13 apply.
$\diamond$

Comment If $0<|{\xiibb S}_{\Gamma}|=N<{\aleph_{0}}$, then $|{\xiibb
P}_{\Gamma}|=2^{N}<{\aleph_{0}}$ and $|{\xiibb
R}_{\Gamma}|=(2^{N})^{2^{N}}<{\aleph_{0}}$. In the finite case, $|{\xiibb
S}_{\Gamma}|<|{\xiibb P}_{\Gamma}|<|{\xiibb R}_{\Gamma}|<{\aleph_{0}}$.

§5.1.8 Definition A constant function $K_{s}:{\xiibb S}\to{\xiibb S}$ is:
$\forall s\in{\xiibb S},\forall x\in{\xiibb S},\;K_{s}(x)=s$.

Comment Every constant function $K_{s}$ is effectively calculable, see §3.1.5.
They are $\lambda$-definable; in $\lambda$-calculus, $K=(\lambda sx.s)$. This
is because our $\lambda$-calculus includes the $K$ combinator, and so we refer
to the $\lambda K$-calculus simply as $\lambda$-calculus.

Special cases Tautology: $K_{\top}=P_{\tau}$. Contradiction:
$K_{\bot}=P_{\bar{\tau}}$. See §3.1.11.

§5.1.9 Definition The constant isomorphism is the natural isomorphism between
${\xiibb S}$ and the set of constant functions ${\xiibb K}$ that relates each
$s\in{\xiibb S}$ with $K_{s}\in({\xiibb S}\to{\xiibb S})$. That is, ${\xiibb
S}\Leftrightarrow{\xiibb K}:s\leftrightarrow K_{s}$.

Comment We can extend any operation on $\xiibb S$ to $\xiibb K$. For example,
for any binary operation $*$ on $\xiibb S$, we define $\forall
x,\,[K_{a}*K_{b}](x)=K_{a}(x)*K_{b}(x)=a*b=K_{a*b}(x)$.

Comment Semantics is included in syntax, that is, ${\xiibb S}\cong{\xiibb
K}\subset({\xiibb S}\to{\xiibb S})$.

§5.1.10 Remark A semantic function $f:{\xiibb S}\to{\xiibb S}$ is a syntactic
element, $f\in({\xiibb S}\to{\xiibb S})$, but it is not a syntactic function
${\xiifrak f}\in(({\xiibb S}\to{\xiibb S})\to({\xiibb S}\to{\xiibb S}))$,
because the semantic function $f$ takes semantic elements and returns semantic
elements, while, using the constant isomorphism, the syntactic function
$\xiifrak f$ is not restricted. In particular, a semantic function cannot take
a function, and a semantic function cannot return a function.

Comment In semantics, literal identity $i$ is the identity, see §4.3.9,
because there are not higher order functions in semantics. But, different
syntactic objects can refer to the same semantic object, as in $f(x)=y$, which
means that $f(x)$ and $y$ are two syntactic objects that refer to the same
semantic object. Then, there are two identities in syntax: literal identity
$\xiifrak i$, or quotation, which is the semantic function that just returns
what it takes, and functional identity $\xiifrak u$, or evaluation, which is
the syntactic function that follows the references and returns the final one,
see §4.2.3. Note also that a syntactic object can refer to no semantic object,
and then we say that the syntactic object is a paradox.

§5.1.11 Definition The range of a resolver $\Re$, noted $\Xi\Re$, is the set
of the problems for which $\Re$ provides a non-empty subset of solutions, and
only of solutions, that is,
$\Xi\Re=\\{\,\pi\mid\Re(\pi)\\!\subseteq\\!\Sigma_{\pi}\land\Re(\pi)\\!\neq\\!\emptyset\,\\}$.

Comment The range of a resolver is the set of the problems that the resolver
solves.

§5.1.12 Definition The power of a resolver $\Re$, noted $\Phi{\Re}$, is the
set of the problems that the resolver $\Re$ resolves, that is,
$\Phi{\Re}=\\{\,\pi\mid\Re(\pi)=\Sigma_{\pi}\,\\}$.

Comment In practice, if $|\Sigma_{\pi}|>1$, it is not sensible to generate all
the solutions, $\Sigma_{\pi}$, when just one solution solves the problem. In
these cases the range of the resolver is more important than its power.

§5.1.13 Theorem $\forall\Re$, ${\cal S}\cap\Phi\Re\subseteq\Xi\Re$.

Proof Because $\forall\pi\in\Phi\Re\cap{\cal S}$, we have that $\pi\in\Phi\Re$
so $\Re(\pi)=\Sigma_{\pi}$, see §5.1.12, and then
$\Re(\pi)\subseteq\Sigma_{\pi}$, and also that $\pi\in{\cal S}$, so
$|\Sigma_{\pi}|>0\Leftrightarrow\Sigma_{\pi}\neq\emptyset$, see §4.5.8 and
§3.2.14, and then $\Re(\pi)=\Sigma_{\pi}\neq\emptyset$, and therefore
$\pi\in\Xi\Re$, see §5.1.11. $\diamond$

Comment For solvable problems, $\Phi\Re\subseteq\Xi\Re$, so they are easier to
solve than to resolve. But unsolvable problems, some of them resolved, are
impossible to solve!

§5.1.14 Definition We will say that the resources of a resolver are in a set
if the capability implemented in the resolver belongs to that set.

Comment Now we will construct a series of resolvers $\Re_{n}$, from the
minimal one that only implements one solution, and then growing naturally step
by step. Each resolver will implement just one element out of its resources

Notation We will use $\\{\cdot\,\Re_{n}\,\cdot\\}$ to refer to the set of all
the resolvers of step $n$.

§5.2 Mechanism

§5.2.1 Definition A mechanism $\Re_{0}$ is any resolver that implements one
member of $\xiibb S$. We will note $\Re_{0}[s]$, where $s\in{\xiibb S}$, the
mechanism that implements $s$, that is, $\Re_{0}[s]=s\in{\xiibb S}$. Then the
mechanisms resources are in $\xiibb S$, and
$\\{\cdot\,\Re_{0}\,\cdot\\}={\xiibb S}$.

Comment Mechanism $\Re_{0}[s]$ returns $s$ unconditionally.

Comment A mechanism $\Re_{0}$ implements a semantic unconditional computation.

§5.2.2 Notation As resolutions return sets of elements in $\xiibb S$, to
normalize the situation of mechanisms $\Re_{0}$ we will use the singleton
isomorphism, see §3.2.11, and we will write $\Re_{0}[\\{s\\}]$ to mean the
singleton $\\{s\\}$, that is, $\Re_{0}[\\{s\\}]=\\{\Re_{0}[s]\\}=\\{s\\}\in
2^{\xiibb S}$.

§5.2.3 Lemma $\forall s\in{\xiibb S}$, $\Xi\Re_{0}[\\{s\\}]=\\{\,\pi\mid
P_{\pi}(s)\,\\}$.

Proof Just applying the definition of range, see §5.1.11, to the definition of
mechanism, we get:
$\Xi\Re_{0}[\\{s\\}]=\\{\,\pi\mid\Re_{0}[\\{s\\}]\\!\subseteq\\!\Sigma_{\pi}\land\Re_{0}[\\{s\\}]\\!\neq\\!\emptyset\,\\}=\\{\,\pi\mid\\{s\\}\\!\subseteq\\!\Sigma_{\pi}\land\\{s\\}\\!\neq\\!\emptyset\,\\}=\\{\,\pi\mid
s\\!\in\\!\Sigma_{\pi}\land\top\,\\}=\\{\,\pi\mid
s\in\Sigma_{\pi}\,\\}=\\{\,\pi\mid P_{\pi}(s)\,\\}$. $\diamond$

Comment The range of the mechanism $\Re_{0}[s]$ is the set of problems for
which $s$ is a solution.

§5.2.4 Lemma $\forall s\in{\xiibb S}$,
$\Phi\Re_{0}[\\{s\\}]=\\{\delta_{s}\\}$.

Proof Just applying the definition of power, see §5.1.12, to the definition of
mechanism, we get:
$\Phi\Re_{0}[\\{s\\}]=\\{\,\pi\mid\Re_{0}[\\{s\\}]=\Sigma_{\pi}\,\\}=\\{\,\pi\mid\\{s\\}=\Sigma_{\pi}\,\\}=\\{\delta_{s}\\}$,
the last equation because $\Sigma_{\delta_{s}}=\\{s\\}$, see §4.3.14.
$\diamond$

Comment Mechanism $\Re_{0}[s]$ only resolves problem $\delta_{s}$.

§5.2.5 Lemma Any singleton routine resolution $R_{\pi}=\\{s\\}$ can be
implemented by the mechanism $\Re_{0}[R_{\pi}]$.

Proof If $R_{\pi}=\\{s\\}$, then
$R_{\pi}=\\{s\\}=\\{\Re_{0}[s]\\}=\Re_{0}[\\{s\\}]=\Re_{0}[R_{\pi}]$.
$\diamond$

Comment In theory, we can equal any finite routine resolution to a union of a
finite number of mechanisms,
$R_{\pi}=\Sigma_{\pi}=\bigcup_{s\in\Sigma_{\pi}}\\{s\\}=\bigcup_{s\in\Sigma_{\pi}}\\{\Re_{0}[s]\\}$.

§5.2.6 Summary In practice, it only makes sense to implement one solution, as
$\Re_{0}[s]$ does. Without conditional calculations, the mechanism could not
control when to apply one result or any of the others, so it would gain
nothing implementing more than one.

Comment The mechanism is a body capable of one behavior.

Example A mechanism can only survive in a specific and very stable
environment, as it is the case of some extremophile archaea.

§5.3 Adapter

§5.3.1 Definition An adapter $\Re_{1}$ is any resolver that implements one
condition on the members of $\xiibb S$. We will note $\Re_{1}[P_{S}]$ the
adapter that implements $P_{S}$, where $P_{S}\in({\xiibb S}\to{\xiibb B})$,
that is, $\Re_{1}[P_{S}]=P_{S}\in({\xiibb S}\to{\xiibb B})$. Then the adapters
resources are in ${\xiibb S}\to{\xiibb B}$, and
$\\{\cdot\,\Re_{1}\,\cdot\\}=({\xiibb S}\to{\xiibb B})$.

Comment An adapter $\Re_{1}$ implements a semantic conditional computation.

§5.3.2 Lemma Each adapter $\Re_{1}[P_{S}]$ implements one set of elements of
$\xiibb S$.

Proof Because every predicate $P_{S}$ defines a set $S=\\{\,s\in{\xiibb S}\mid
P_{S}(s)\,\\}\in 2^{\xiibb S}$. The condition $P_{S}$ is the characteristic
function of $S$, $\forall s\in{\xiibb S},\;P_{S}(s)=[s\in S]$. $\diamond$

Comment We will write $\Re_{1}[P_{S}]=\Re_{1}[S]=S\in 2^{\xiibb S}$. Only
effectively calculable conditions are implementable, and then adapters can
only implement expressible, or recursive, sets, $\cal E$. Then,
$\Re_{1}[P_{S}]=\Re_{1}[S]=S\in{\cal E}$.

§5.3.3 Lemma Every mechanism $\Re_{0}$ is an adapter $\Re_{1}$, that is,
$\\{\cdot\,\Re_{0}\,\cdot\\}\subset\\{\cdot\,\Re_{1}\,\cdot\\}$.

Proof For each mechanism $\Re_{0}[s]$, which implements $s\in{\xiibb S}$,
there is an adapter $\Re_{1}[P_{\delta_{s}}]$, see §4.3.14, that implements
the singleton $\\{s\\}\in({\xiibb S}\to{\xiibb B})$. But not every set is a
singleton. Summarizing, $\\{\cdot\,\Re_{0}\,\cdot\\}={\xiibb S}\subset({\xiibb
S}\to{\xiibb B})=\\{\cdot\,\Re_{1}\,\cdot\\}$. $\diamond$

Comment In Cantor’s paradise, but out of Turing universes, by the singleton
(§3.2.11) and the set (§3.2.8) isomorphisms:
$\\{\cdot\,\Re_{0}\,\cdot\\}={\xiibb S}\cong{\xiibb S}^{1}\subset 2^{\xiibb
S}\cong({\xiibb S}\to{\xiibb B})=\\{\cdot\,\Re_{1}\,\cdot\\}$.

§5.3.4 Lemma $\Re_{1}[S]=\bigcup_{s\in S}\\{\Re_{0}[s]\\}$.

Proof Because $\Re_{0}[s]=s$, so $\bigcup_{s\in
S}\\{\Re_{0}[s]\\}=\bigcup_{s\in S}\\{s\\}=S=\Re_{1}[S]$. $\diamond$

Comment The results are the same, but not the implementation, because while
the adapter $\Re_{1}[S]$ implements a condition, the union of mechanisms
$\bigcup_{s\in S}\\{\Re_{0}[s]\\}$ works unconditionally. Thus, the output of
the union of mechanisms is independent of any problem, and then the union
cannot implement $\Re_{1}[P_{S}\land P_{\pi}]=\Re_{1}[S\cap\Sigma_{\pi}]$, for
example, so it cannot implement any trial, see Theorem §3.3.5.

§5.3.5 Lemma $\forall S\in 2^{\xiibb S}$, $\forall\pi\in{\xiibb P}$,
$\Xi\Re_{1}[S\cap\Sigma_{\pi}]=\\{\,\pi\mid
S\cap\Sigma_{\pi}\neq\emptyset\,\\}$.

Proof Because
$\Xi\Re_{1}[S\cap\Sigma_{\pi}]=\\{\,\pi\mid(\Re_{1}[S\cap\Sigma_{\pi}]\subseteq\Sigma_{\pi})\land(\Re_{1}[S\cap\Sigma_{\pi}]\neq\emptyset)\,\\}=\hbox{}\hfil\break\\{\,\pi\mid(S\cap\Sigma_{\pi}\subseteq\Sigma_{\pi})\land(S\cap\Sigma_{\pi}\neq\emptyset)\,\\}=\\{\,\pi\mid\top\land(S\cap\Sigma_{\pi}\neq\emptyset)\,\\}=\hbox{}\hfil\break\\{\,\pi\mid
S\cap\Sigma_{\pi}\neq\emptyset\,\\}$. $\diamond$

Comment The range of the adapter $\Re_{1}[S\cap\Sigma_{\pi}]$ is the set of
problems that have any solution in $S$. The adapter
$\Re_{1}[S\cap\Sigma_{\pi}]$ solves any problem such that any of its solutions
are in $S$.

Corollary If $S\subset S^{\prime}$, then
$\Xi\Re_{1}[S\cap\Sigma_{\pi}]\subset\Xi\Re_{1}[S^{\prime}\cap\Sigma_{\pi}]$.

Proof In that case, if a solution to a problem is in $S$, then it is also in
$S^{\prime}$. But there are also solutions in $S^{\prime}$ that are not in
$S$. $\diamond$

§5.3.6 Lemma If $s\in S$, then $\forall\pi\in{\xiibb P}$,
$\Xi\Re_{0}[\\{s\\}]\subseteq\Xi\Re_{1}[S\cap\Sigma_{\pi}]$.

Proof By Lemma §5.2.3, $\forall\pi\in\Xi\Re_{0}[\\{s\\}]$, $P_{\pi}(s)$, that
is, $s\in\Sigma_{\pi}$, so, if $s\in S$, then
$S\cap\Sigma_{\pi}\neq\emptyset$, and therefore
$\pi\in\Xi\Re_{1}[S\cap\Sigma_{\pi}]$, by Lemma §5.3.5. $\diamond$

Definition We will call $s\in S$ the adapter condition. If the adapter
condition holds, then the adapter $\Re_{1}[S\cap\Sigma_{\pi}]$ solves any
problem that the mechanism $\Re_{0}[s]$ solves.

Corollary If $\\{s\\}\subset S$, then
$\Xi\Re_{0}[\\{s\\}]\subset\Xi\Re_{1}[S\cap\Sigma_{\pi}]$.

Proof Because, if $t\in S$ and $t\neq s$, then
$\delta_{t}\in\Xi\Re_{1}[S\cap\Sigma_{\pi}]$ but
$\delta_{t}\not\in\Xi\Re_{0}[\\{s\\}]$. $\diamond$

Proposition If $\\{s\\}\subset S$, then
$\Xi\Re_{0}[\\{s\\}]\not\subset\Xi\Re_{1}[S]$. Because
$\delta_{s}\in\Xi\Re_{0}[\\{s\\}]$, but $\delta_{s}\not\in\Xi\Re_{1}[S]$.

§5.3.7 Lemma $\forall S\in 2^{\xiibb S}$, $\forall\pi\in{\xiibb P}$,
$\Phi\Re_{1}[S\cap\Sigma_{\pi}]=2^{S}$.

Proof Because
$\Phi\Re_{1}[S\cap\Sigma_{\pi}]=\\{\,\pi\mid\Re_{1}[S\cap\Sigma_{\pi}]=\Sigma_{\pi}\,\\}=\\{\,\pi\mid
S\cap\Sigma_{\pi}=\Sigma_{\pi}\,\\}=\hbox{}\hfil\break\\{\,\pi\mid\Sigma_{\pi}\subseteq
S\,\\}=2^{S}$, where the last equality uses the set isomorphism, see §3.2.8.
$\diamond$

Comment The power of the adapter $\Re_{1}[S\cap\Sigma_{\pi}]$ is the powerset
of $S$. The adapter $\Re_{1}[S\cap\Sigma_{\pi}]$ resolves any problem such
that all of its solutions are in $S$.

Corollary If $S\subset S^{\prime}$, then
$\Phi\Re_{1}[S\cap\Sigma_{\pi}]\subset\Phi\Re_{1}[S^{\prime}\cap\Sigma_{\pi}]$.

Proof Just because, if $S\subset S^{\prime}$, then $2^{S}\subset
2^{S^{\prime}}$. $\diamond$

§5.3.8 Lemma If $s\in S$, then $\forall\pi\in{\xiibb P}$,
$\Phi\Re_{0}[\\{s\\}]\subset\Phi\Re_{1}[S\cap\Sigma_{\pi}]$.

Proof Using the set isomorphism, see §3.2.8,
$\delta_{s}=\Sigma_{\delta_{s}}=\\{s\\}$, and then, if $s\in S$,
$\Phi\Re_{0}[\\{s\\}]=\\{\delta_{s}\\}=\\{\\{s\\}\\}\subset
2^{S}=\Phi\Re_{1}[S\cap\Sigma_{\pi}]$, by Lemmas §5.2.4 and §5.3.7. $\diamond$

Comment If the adapter condition holds, $s\in S$, then the adapter
$\Re_{1}[S\cap\Sigma_{\pi}]$ resolves any problem that the mechanism
$\Re_{0}[s]$ resolves, and more.

Proposition If $\\{s\\}\subset S$, then
$\Phi\Re_{0}[\\{s\\}]\not\subset\Phi\Re_{1}[S]$, because
$\delta_{s}\not\in\Phi\Re_{1}[S]=\\{S\\}$.

§5.3.9 Lemma Any effectively calculable trial resolution $T_{\pi}(S)$ can be
implemented by the adapter $\Re_{1}[S\cap\Sigma_{\pi}]$.

Proof $T_{\pi}(S)=\\{\,s\in S\mid s\in\Sigma_{\pi}\,\\}=\\{\,s\mid
s\\!\in\\!S\land s\\!\in\\!\Sigma_{\pi}\,\\}=\\{\,s\mid P_{S}(s)\land
P_{\pi}(s)\,\\}$. Then $T_{\pi}(S)\doteq\Re_{1}[P_{S}\land
P_{\pi}]=\Re_{1}[S\cap\Sigma_{\pi}]$. The equality is dotted because, if the
trial is not an effectively calculable function, then it cannot be
implemented. $\diamond$

§5.3.10 Summary In practice, an adapter $\Re_{1}[P_{S}\land
P_{\pi}]=\Re_{1}[S\cap\Sigma_{\pi}]$ has a body capable of several behaviors
that provides the set $S$ of behaviors. If the current behavior were not
satisfying the adapter condition $P_{\pi}$, which is interpreted as an error,
then the adapter would change its behavior trying another one in $S$.

Comment The adapter is a body capable of several behaviors, and a governor
that selects the current behavior.

Example A deciduous tree, which switches its behavior with seasons, is an
adapter.

§5.4 Perceiver

§5.4.1 Definition A perceiver $\Re_{2}$ is any resolver that implements one
transformation of the elements in $\xiibb S$ into the elements in $\xiibb S$.
We will note $\Re_{2}[f]$ the perceiver that implements $f$, where
$f\in({\xiibb S}\to{\xiibb S})$, that is, $\Re_{2}[f]=f\in({\xiibb
S}\to{\xiibb S})$. Then the perceiver resources are in ${\xiibb S}\to{\xiibb
S}$, and $\\{\cdot\,\Re_{2}\,\cdot\\}=({\xiibb S}\to{\xiibb S})$.

Comment From a semantic point of view, a perceiver $\Re_{2}$ implements a
semantic functional computation. From a syntactic point of view, a perceiver
$\Re_{2}$ implements a syntactic unconditional computation.

§5.4.2 Remark Perceivers are to syntax as mechanisms are to semantics.

Comment When solutions are functions ${\xiibb S}\to{\xiibb S}$, then a
perceiver does what a mechanism does, which is to return a solution
unconditionally. That is, perceivers on metaproblems are as mechanisms on
problems. But, perceivers can go further.

Comment The perceiver $\Re_{2}[f]$ implements function $f$ from ${\xiibb S}$
to ${\xiibb S}$, that is, $f:{\xiibb S}\to{\xiibb S}$. Then, $\forall
s\in{\xiibb S},\;\Re_{2}[f](s)=f(s)\in{\xiibb S}$.

§5.4.3 Notation By the rewriting rules in §3.1.3,
$\Re_{2}[f](S)=\\{\,\Re_{2}[f](s)\mid s\in S\,\\}\in 2^{\xiibb S}$. Then
$\Re_{2}[f](S)$ returns a set of solutions, as any well-behaved resolution
should do.

Comment The perceiver $\Re_{2}[f](S)$ implements $f$, meaning that $f$ is
hardwired in the perceiver, while $S$ is just data. We will call what is
implemented hardware, and what is data software. We write the hardware between
brackets, and the software between parentheses. We will assume that coding
software costs less than implementing hardware, or, in fewer words, that
software is cheaper than hardware

§5.4.4 Lemma Every adapter $\Re_{1}$ is a perceiver $\Re_{2}$, that is,
$\\{\cdot\,\Re_{1}\,\cdot\\}\subset\\{\cdot\,\Re_{2}\,\cdot\\}$.

Proof Because ${\xiibb B}\subset{\xiibb S}$, and then $({\xiibb S}\to{\xiibb
B})\subset({\xiibb S}\to{\xiibb S})$. So $\\{\cdot\,\Re_{1}\,\cdot\\}=({\xiibb
S}\to{\xiibb B})\subset({\xiibb S}\to{\xiibb S})=\\{\cdot\,\Re_{2}\,\cdot\\}$.
$\diamond$

Comment Each adapter implements one condition $P_{S}\in({\xiibb S}\to{\xiibb
B})$. And any condition $P_{S}\in({\xiibb S}\to{\xiibb B})$ is also a function
$P_{S}\in({\xiibb S}\to{\xiibb S})$, because ${\xiibb B}\subset{\xiibb S}$.
Therefore, for each adapter $\Re_{1}[P_{S}]$, which implements condition
$P_{S}$, there is a perceiver $\Re_{2}[P_{S}]$ that implements the function
$P_{S}$, and then we write $\Re_{1}[P_{S}]=P_{S}=\Re_{2}[P_{S}]$.

Comment Again, $\Re_{1}[P_{S}]=\Re_{2}[P_{S}]$ explains that the results are
the same, but not the implementation.

§5.4.5 Lemma $\forall S\in 2^{\xiibb S},\;\Re_{1}[S]=\Re_{2}[i](S)$.

Proof Function $i:{\xiibb S}\to{\xiibb S}$ is the semantic identity,
$i={\xiifrak i}$ see §5.1.10, so $\forall s\in{\xiibb S},\;i(s)=s$, and
$\Re_{2}[i](S)=\\{\,\Re_{2}[i](s)\mid s\in S\,\\}=\\{\,i(s)\mid s\in
S\,\\}=\\{\,s\mid s\in S\,\\}=S=\Re_{1}[S]$. $\diamond$

Comment The same perceiver hardware $\Re_{2}[i]$, just by changing its
software, can emulate different adapters: $\Re_{2}[i](S)=\Re_{1}[S]$, and
$\Re_{2}[i](S^{\prime})=\Re_{1}[S^{\prime}]$. Then the perceiver
$\Re_{2}[i](S)$ is more flexible than the adapter $\Re_{1}[S]$, because $S$ is
hardwired in the adapter, while it is easily replaceable data for the
perceiver.

§5.4.6 Lemma $\forall S\in 2^{\xiibb S}$, $\Xi\Re_{1}[S]=\Xi\Re_{2}[i](S)$ and
$\Phi\Re_{1}[S]=\Phi\Re_{2}[i](S)$.

Proof Because, by Lemma §5.4.5, $\Re_{1}[S]=\Re_{2}[i](S)$. $\diamond$

Definition The perceiver condition is satisfied if it implements the semantic
identity $i$.

Comment If the perceiver condition holds, then the perceiver $\Re_{2}[i](S)$
solves any problem solved by the adapter $\Re_{1}[S]$, and the perceiver
$\Re_{2}[i](S)$ resolves any problem resolved by the adapter $\Re_{1}[S]$.

Remark Semantic identity $i$ is the ideal for perception.

§5.4.7 Corollary
$\Xi\Re_{2}[i](S\cap\Sigma_{\pi})=\Xi\Re_{1}[S\cap\Sigma_{\pi}]$ and
$\Phi\Re_{2}[i](S\cap\Sigma_{\pi})=\Phi\Re_{1}[S\cap\Sigma_{\pi}]$.

Proof By Lemma §5.4.6. $\diamond$

Comment The same perceiver hardware $\Re_{2}[i]$ can be tuned to a different
trial just by changing its software, from $\Re_{2}[i](S\cap\Sigma_{\pi})$ to
$\Re_{2}[i](S^{\prime}\cap\Sigma_{\rho})$, for example.

Proposition If $S\subset S^{\prime}$, then
$\Xi\Re_{2}[i](S\cap\Sigma_{\pi})\subset\Xi\Re_{2}[i](S^{\prime}\cap\Sigma_{\pi})$,
and
$\Phi\Re_{2}[i](S\cap\Sigma_{\pi})\subset\Phi\Re_{2}[i](S^{\prime}\cap\Sigma_{\pi})$,
by Lemma §5.4.5 and corollaries to Lemmas §5.3.5 and §5.3.7.

§5.4.8 Definition A function on sets $F:2^{\xiibb S}\to 2^{\xiibb S}$ is
elementable if it exists an effectively calculable function $f:{\xiibb
S}\to{\xiibb S}$ such that $\forall S,\;F(S)=\\{\,f(s)\mid s\in S\,\\}$.

Comment We write $F(S)=f(S)$, by the rules in §3.1.3. Note the three
requirements: that $f$ is a semantic function, $f:{\xiibb S}\to{\xiibb S}$,
that $f$ is effectively calculable, and that $F(S)=f(S)$.

Proposition Set identity $I:2^{\xiibb S}\to 2^{\xiibb S}\mid\forall S\in
2^{\xiibb S},\;I(S)=S$, is elementable by semantic identity $i$, because
$\forall S\in 2^{\xiibb S},\;i(S)=\\{\,i(s)\mid s\in S\,\\}=\\{\,s\mid s\in
S\,\\}=S=I(S)$.

§5.4.9 Lemma Any analogy resolution $A\circ T_{A\pi}(S)\circ{\cal T}_{A}$ can
be implemented by the tri-perceiver $\Re_{2}[{\cal
T}_{a}](\Re_{2}[i](S\cap\Re_{2}[a](\Sigma_{\pi})))$, if $A$ is elementable by
$a$, and ${\cal T}_{A}$ by ${\cal T}_{a}$.

Proof An analogy resolution is $A\circ{T\\!}_{A\pi}(S)\circ{\cal T}_{A}$. Both
$A$ and ${\cal T}_{A}$ are functions from sets to sets, ${\cal
T}_{A}:2^{\xiibb S}\to 2^{\xiibb S}$ and $A:({\xiibb P}\to{\xiibb
P})=(2^{\xiibb S}\to 2^{\xiibb S})$, so if both $A$ and ${\cal T}_{A}$ are
elementable, then a perceiver can implement them. We have $a$ and ${\cal
T}_{a}$, which are both semantic functions such that $A(S)=a(S)$, and ${\cal
T}_{A}(S)={\cal T}_{a}(S)$. Then
$P_{a\pi}=a(P_{\pi})=\Re_{2}[a](P_{\pi})=\Re_{2}[a](\Sigma_{\pi})$ implements
the first third, ${T\\!}_{a\pi}(S)=\Re_{1}[P_{S}\land
P_{a\pi}]=\Re_{1}[P_{S}\land\Re_{2}[a](P_{\pi})]=\Re_{1}[S\cap\Re_{2}[a](\Sigma_{\pi})]$
implements the second third, see §5.3.9, and using §5.4.5, $\Re_{2}[{\cal
T}_{a}](\Re_{2}[i](S\cap\Re_{2}[a](\Sigma_{\pi})))$ implements the whole
analogy resolution $a\circ T_{a\pi}(S)\circ{\cal T}_{a}$. $\diamond$

Corollary Identity analogy $I\circ T_{I\pi}(S)\circ{\cal T}_{I}$ can be
implemented by the bi-perceiver $\Re_{2}[i](S\cap\Re_{2}[i](\Sigma_{\pi}))$,
which uses the identity perceiver $\Re_{2}[i]$ twice.

Proof $\Re_{2}[{\cal
T}_{i}](\Re_{2}[i](S\cap\Re_{2}[i](\Sigma_{\pi})))=\Re_{2}[i](\Re_{2}[i](S\cap\Re_{2}[i](\Sigma_{\pi})))=\Re_{2}[i](S\cap\Re_{2}[i](\Sigma_{\pi}))$,
because set identity $I$ is elementable by semantic identity $i$, and ${\cal
T}_{I}=I$, so it is also elementable by ${\cal T}_{i}=i$, and $i\circ i=i$.
$\diamond$

§5.4.10 Summary While an adapter uses a trial and error resolution, and this
means that error is part of the usual procedure, a perceiver executes the
trial and error inside itself. If the analogy provides a good model, then the
internal trial is as good as the external one, with the advantage that the
errors are only simulated errors. More to the point, if the problem the