| Turing Machine |
Alternatives
in Computability Research
April 27, 1997
I
plan to examine the status quo in the field of computability and
unsolvability in pure mathematics and theoretical computer science.
One aspect of the status quo seems to be the use of high performance
computing to facilitate the study of the subject, which leads us to a
consideration of possible changes to come.
With
the increasing efficiency and speed of computing equipment the old
high performance computing research model may need to be relegated to
only the most expensive research in terms of computer time. Already
in some fields network communications and parallel processing are
performing computing tasks that once were the sole task of research
supercomputers and mainframes. This phenomenon has occurred in
applications as disparate as filtering applications in radio
astronomy and chess programs used in grandmaster versus machine
matches. Many of the IT labs computer accounts used at the University
of Minnesota are maintained on networks of workstations and not on
mainframes or supercomputers. The continuing trend toward use of
distributed and parallel computing systems is apparent and
inevitable.
With
limited resources and increasing research demands the use of
networked, distributed and parallel systems will become necessary,
thus making now an ideal time to implement this process in
computability and unsolvability research. In fact, this process has
already been occurring for some time in the field. As more and more
specialists from the computer science become involved in automata
theory the situation will only become more favorable with regard to
innovative research. Computer science is a young field in which
paradigms of software development and hardware implementation have
changed many times, and in which different approaches to these
activities have managed to exist simultaneously.
One
of the central concepts of Computability and Unsolvability is the
algorithm. In essence an algorithm is an effective computational
procedure. Intuitively one may think of an algorithm as purely
mechanical sets of instructions which will provide the answer to any
one of a class of questions. These instructions are devoid of any
non-deterministic features, such as the ones often attributed to
human creativity. In theory it will always be possible to fabricate a
machine or program a computer which carries out these instructions.
For example, as school children we were taught algorithms for solving
simple sums. This was done in the past by human clerks who applied
these algorithms to sets of data given them by their overseers. Today
we have adding machines which perform these tasks.i
Consider
a given problem that one wishes to solve. It may not be the case that
one has already at hand an algorithm which will solve it. Now we
ask: is there an algorithm which will solve this problem? We now have
what is known as a decision problem. An affirmative solution to a
decision problem consists in demonstrating the existence of an
algorithm which solves it; a negative solution in showing that no
such algorithm exists. In the latter case the problem is said to be
unsolvable.ii
Showing that a decision problem is unsolvable can save much needless
effort on the part of researchers in mathematics and computer
science.
In
the development of this theory the Turing machine emerged, an
important concept in both mathematics and computer science. A Turing
machine is an abstract model of an automata that applies algorithmic
sets of instructions until it reaches a solution at which point it
halts. It may be visualized as an infinite strip of tape with
infinitely many boxes subdividing it, similar to the manner in which
a strip of film is. There is a scanner or read-write tape head that
can move to the left or to the right along the tape and scans the
information contained in one of the tape subdivisions. The
information contained on each subdivision of the tape is the data
manipulated by the instructions and the instructions themselves. A
digital computer can be thought of as operating in a similar way.
Data is stored in memory locations or cells that contain information
which can be instructions or data, and these locations are scanned
and written to in a certain sense by registers.
The
primary task of the computer programmer is the implementation of
algorithms. A computer program is in essence an algorithm. The
practice of computer programming has shown that essentially the same
algorithm may be implemented in diverse forms. This is because many
different and successful models of program development are in
existence. These different models are motivated just as much, those
more disposed to the point of view of engineering would say more, by
the possibilities of actual technology as by the results of
mathematical logic. One of the main points I covered in my interview
with Dr. Ravi Jarnardan of the University of Minnesota Computer
Science faculty was that mathematical analysis provides the answers
to questions about the performance that can be expected of
algorithms. Consider the problem of sorting n names into alphabetical
order. Analysis has shown that both the bubble sort and straight
insertion sort algorithms will perform nxn operations in worst case
situations. They are expensive algorithms in terms of computer time.
However, it is known widely from experience that the straight
insertion sort algorithm is often much more efficient than the bubble
sort algorithm. Thus an average case analysis may be more relevant in
assessing the relative performances of different algorithms. In the
case of the heapsort algorithm, which is much more efficient than the
aforementioned, a probabilistic analysis which in essence simulates a
coin flip at each stage of the algorithm can be very helpful. For
example, program A takes action X or action Y at stage Z of its
execution. Probabilistic analysis would make the result of the coin
flip correspond with the action the taken by program A. Probabilistic
analysis tries to account for the conditional probability inherent in
the execution of many programs.
On
the software side we have the different approaches of modular
programming and object oriented programming. Modular programming has
been described as top down. In this model the programmer strives to
subdivide the problem he is given into as many smaller simple
subproblems as they can. A module is the program division that
contains the algorithm used to solve these simpler subproblems. A
simple main program calls its functions or modules which then
perform the requisite data processing. This has the advantage that
the given modules can be used various times in the original program
without the need for writing the entire set of instructions again,
thus wasting increasingly not so valuable computer memory. In the
black box approach that is the ideal of modular programming many
different modules, the black boxes, are written for use as they may
be needed at later times by various main programs. In object oriented
programming a class or object which contains its own modules and data
is instantiated, dynamically allocated, implemented and then
destroyed. All in all contemporary computer science students are
expected to be conversant with both software development paradigms.
In part this is because object oriented implementations would make
little sense without the use of modules in them. An example of the
interplay between the two models is the use of object oriented
programming packages to write the compilers used by modular
programming packages. C++ which is considered an object oriented
programming language was used by Microsoft to develop Visual Basic, a
programming package which is more modular in nature.
That
different problems lent themselves to different solution strategies
should be readily apparent. However, these differences in solution
strategy may lie more in what is used to solve the problem, viz.
software and hardware, as in the actual form of the algorithm used to
solve it. I hold that a research team given a set of problems to
resolve could optimize the software and hardware options to be
implemented. Thus an algorithm that needed to bounce back and forth
checking and comparing integers thirty octillion times would be well
suited for FORTRAN code and compilers. Research that pertained to
more complicated recursive functions or decision procedures that need
to evaluate whole classes of objects and not just cheap integers
would be more appropriate for parallel computing using object
oriented code or a language package used in computer science or
artificial intelligence such as LISP, Ada, Smalltalk, Prolog etc..
Several
alternative approaches to problems in the field of computability and
unsolvability have already been outlined in the proceeding
paragraphs. For example, supercomputer and mainframe processing of
expensive numerical algorithms, niche languages and specialty items
optimized for use in restricted applications such as the prolog
computer language. On the hardware side we have parallel or
distributed computing projects among the many alternatives. Where
alternatives exist one of course always has the opportunity to fuse
them together into a hybrid project that is well fitted to those
aspects of the problem in question which are themselves of a hybrid
nature.
Among
the benefits of such an integrated and synthetic approach would be
the mutual contributions that computer science and mathematics have
to give each other. In utilizing the tools of computer science to
further the mathematical endeavor computer scientists would see their
software design and hardware implementation in action. Mathematicians
would see the fruits of their theoretical labors in mathematics
applied to and come to fruition in computer science. At times it is
possible to have the best of both worlds. On an intuitive level one
should be able to see how the possible project optimization proposal
I gave above could be useful. However, as the old cliché says, too
many cooks can spoil the broth. One would have to be careful that the
proliferation of alternative approaches did not result in a
concomitant proliferation of problems. At other times, one has the
worst of both worlds. Also there are those schooled in the old ways
who have much experience to offer the inquirer. Standard and time
honored approaches to certain problems are often the most
accommodating for the greatest number.
No comments:
Post a Comment