Information Technology Reference
In-Depth Information
Teaching the theory of effective computability means more than introducing
some particular computability concept like partial recursive functions as above.
Fundamental educational goals are
-
an understanding of the generality of the varying classical approaches to
effective computability,
-
an understanding of several key results such as
Rice
's theorem and their
fundamental, so to speak, philosophical interpretation,
-
an understanding and an operational interpretation of syntactic results such
as
Kleene
's normal form theorem,
-
the mastery of some application cases by means of an interpretation and an
application of fundamental results.
The question for the deployment of new media and innovative approaches to
teaching and learning to rather abstract contents is throwing some new light at
the key results of recursive function theory. Some results are more amenable to
exploratory studies than others.
Let us have a closer look at
Kleene
's normal form theorem [13] (see also
[15],
2.1, not numbered).
Here are the results in comparison valid for any so-called
Godel
numbering
ϕ
IN
is the set of natural numbers,
Pr
is the class of primitive recursive functions,
R
§
1.10, Theorem X) and
Rice
's theorem [16] (see [15],
§
is the class of partial recursive
functions and
μ
denotes the minimum operator:
Kleene
's Theorem
∃
is the class of total recursive functions,
P
α, β
∈
Pr
∀
f
∈P∃
n
∈
IN
∀
x
∈
INf
(
x
)=
α
(
μy
[
β
(
x, y
)=0])
Rice
's Theorem
∀
)
It is di
cult to imagine that human learners get a better understanding of
Rice
's
theorem by any way of playing around with certain recursive function definitions.
In contrast, one may set up numerous exercise which essentially deal with
Kleene
's normal form theorem. Take any definition of some partial recursive
function which contains two nested calls of the minimum operator. Ask the
students to find another definition which is equivalent to the given one, but
contains only a single occurrence of the minimum operator. The appropriateness
of the task is guaranteed by the
Kleene
normal form theorem.
By the way, pondering the equivalence of the definition given to the students
to the students' solution is an interesting scientific problem in its own right.
Let us summarize this section briefly. The theory of effective computability is
quite involved. Some results have an enormous reach, but are dicult to master.
A mastery of the theory of effective computability does definitely require some
intensive studies and may be hardly achieved just through some playful activities.
But pondering the essentials of such an involved theory may be substantially
supported by providing technologies and tools for some exploratory endeavor-
exploring and understanding the abstract by direct manipulation of the concrete
.
F
⊆P∀
d
∈R
((
∀
n
∈
INd
(
n
)=0
↔
ϕ
n
∈
F
)
←→
F
=
∅∨
F
=
P
