Information Technology Reference
In-Depth Information
2 Teaching the Theory of Effective Computability
For studying computer science, it is of some relevance to know what can be done
by means of digital processing technology and where the limits are. When facing
particular application problems, it frequently helps to relate them to already
known problems and to insights about their principle solvability and complexity.
In particular, when facing some essentially unsolvable problem, it might be nice
to learn about the problem's hardness as early as possible.
Computability theory
(known under many different names including terms
such as
recursion theory
,
recursive function theory
, and the like) is providing the
basic concepts, methodologies, and insights [9,12,14,15].
Due to its generality, the theory of effective computability relies on involved
mathematical theories and methods. Consequently, many students who misun-
derstood informatics as a discipline of hacking code according to ones own taste
are having particular diculties with a firm foundation.
There is a widespread practice of teaching computability theory like a course
in mathematics. The results are frequently disappointing.
Computation, by its very nature, usually proceeds in small steps, one by one.
Particular models such as so-called
Turing
machines reflect this explicitly. Some
other approaches such as the hierarchical definition of partial recursive functions
are more algebraic in spirit. There are initial constituents and certain operators.
In an algebraic sense, such a system uniquely defines the smallest class of objects
containing all the initial constituents and being closed under the operations.
Such a, so to speak, algebraic approach to computability assumes as initial
objects a couple of functions and operators as follows. For simplicity, one usually
considers functions defined over the set of natural numbers.
-
The initial functions are
•
the unary successor function
s
,
•
the
n
-ary constant functions
c
k
with
c
k
(
x
1
,...,x
n
)=
k
,
•
the
n
-ary projection functions
p
k
with
p
k
(
x
1
,...,x
n
)=
x
k
.
-
The primitive operations are
•
substitution,
primitive recursion.
-
The operation completing the approach is called
•
•
the minimum operator.
Note that there are enormously many simplifications possible. Due to the avail-
ability of the successor function
s
, there is no need for any other constant func-
tions than the zero constants
c
0
, just for instance.
When you stick with explanations of how to define any computable function
on the basis of these initial functions using the possibly repeated application of
the three operators, it remains a course in mathematics.
Therefore, there have been developed and implemented meme media variants
of all the constituents above [1]; see the following section. Having those meme
media objects at your fingertips, you may playfully experiment by plugging one
into the other. The feature of stepwise computation shows again.
