Question

1. Explain how Kugel (1986) proposes that we attempt to mimic the uncomputable nature of human thought and reasoning in intelligent machines. Provide an example of a real-life application in an existing uncomputable AI project. Reference your source(s).

Answer 1

1. Introduction
It seems, to me, that parts of thinking may require more than computing. But that does not seem, to me, to mean that those parts cannot be studied scientifically. In this paper, I want to suggest some ways that the uncomputa- ble parts of thinking might be studied with much the same precision, and in very much the same spirit, that Turing suggested for the study of its comput- able parts. In his famous paper on “Computing machinery and intelligence” (Turing, 1950), Turing observed that one of the things that makes it difficult to study the relationship between thinking and computing is that, although we have a precise definition of “computing”, we lack a precise definition of “thinking”. Therefore, he suggested that, rather than try to study the whole of thinking (which we cannot define), we try to study specific parts of thinking (which we can point to). Let us, he proposed, look at specific activities that seem to require thinking and try to develop computable models for them, one at a time. When we succeed, the models we develop may tell us something about the parts of thinking that we have modelled. I want to suggest that we might do much the same thing with the uncom- putable parts of thinking. Let us look at parts of human thinking that seem (to some of us) to involve more than computing and try to develop precise uncomputable models of them. Insofar as our models are correct, they may tell us something about the uncomputable parts of thinking with much the same kind of precision that we now get from our computable models. Turing’s paper was addressed primarily to what we might think of as the engineering approach to the mind, in which we try to develop (or program) machines that do what the mind does. But his suggestion also applies to the scientific approach to the mind, in which we try to explain or predict what the mind does. One reason that uncomputable accounts of the mind can be precise is that, like computable accounts, they can be represented by computer (but not by computing) programs. Computers can, in spite of what we call them in En- glish, be used to do more than compute. (The fact that we call a machine a “computer” no more limits it to computing than the fact that we call a person “foolish” limits that person to foolishness.) Thinking may lie within the range of what a computer can do and still lie beyond the range of what it can do by computing alone. Turing suggested precisely this possibility in his 1950 paper. He devoted most of that paper to arguing that computers might be able to duplicate most of the behavior that, when people do it, we call “think- ing”. But, toward the end of his paper, he briefly suggested that they might also have to do more than computing to do it. Wrote Turing (1950): Intelligent behaviour presumably consists in a departure from the completely disciplined behaviour involved in computation, but a rather slight one which does not give rise to random behaviour or pointless repetitive loops.
Cognitive Science now takes the first part of Turing’s suggestion (that computers can model thinking) quite seriously. In this paper, I want to suggest that the time may have come to take the second part (that they will have to do more than to computing to do it) more seriously than we have been. The main aim of this paper is to suggest a way that this might be done systematically, using ideas from the mathematical theory of the uncomputa- ble, or Recursion Theory.

2. How computers might do more than compute
To see how a computer might do more than compute, consider an idealized general-purpose computing machine, M. When we use M, we first give it a program, p, and an input, inp. We then let it run, step by deterministic step, following the instructions of p, to process inp. We will refer to the process of M, running under program, p, on input, inp, as “M,(inp)“. From time to time, M,(inp) may print something. We will call anything it prints an “out- put”. Since we will focus primarily on processes that make simple yes/no decisions, we will begin by limiting M’s outputs to YES and NO. That is not as restrictive as it might, at first, appear and the generalization to more complex outputs is relatively straightforward. We distinguish an output from a result. An output is anything M prints, whereas a result is a selection, from among the things it prints, that we agree to pay attention to. This distinction is not important when we limit ourselves to computations because, when we use M to compute, we agree to pay atten- tion only to the first thing that it prints and often turn it off (or over to another job) once it has printed that. Thus its result and (only) output are one and the same. Many problems can be solved by computations. Others can not. Among those that can not is: The Full Halting Problem. Given a program, p, and an input, i, to determine whether or not M,(i) (M, running under program, p, on input, i) will or will not halt (eventually). A (totally) computable solution to this problem would be a computing procedure, controlled by a single program, h, such that M&,i) (M, running under program h, on the input (p,i)) computes: YES when M,(i) halts NO when it does not. There can be no such computing M,, that produces the correct YES’s and NO’s for all possible input pairs (p,i). However, a partially computable Mh, that produces only the YES’s, is possible. (See the Appendix for an outline of the proofs.) A different kind of procedure, that I will call (following Putnam, 1965) a total trial and error procedure, can produce both the YES’s and the NO’s. (The idea of a trial and error procedure was developed, apparently indepen- dently, by Putnam (1965) and Gold (1965). Precursors of the idea can be found in Shoenfield (1967)) Popper (1959)) in Leibnitz’s (1956) writings about induction and in the work of Xenophanes (fragments 189 and 191 in Kirk and Raven, 1957).) The difference between a computing procedure and a trial and error procedure is this. When we run Mp as a computing procedure, we count its first output as its result. When we run it as a trial and error proce- dure, we count its lust output as its result. This makes a difference for, although no computing procedure can solve the Full Halting Problem, a total trial and error procedure can. For example, let M,(p,i) start off by printing NO. Then let it simulate (imitate) M,(i), step by step. If the simulation halts, let it print YES and halt. Count, as Mb’s result, the lust output that it prints. It is easy to see that this defines a trial and error procedure and that the result that M, produces, under this way of interpreting its outputs, is always a correct solution to the Full Halting Problem. Notice that a machine running a trial and error procedure looks just like a machine running a computing procedure. It uses no special “hardware” and certainly no “magic”. Its result is produced, like that of a computation, in finite time using only finitely much memory. But there is an important differ- ence. When a computation (say to determine the value of 12 + 13) comes up with a result (25), we know that that is the result. But when a trial and error procedure (say to determine whether Fermat’s Last Theorem is true by checking, systematically, through all possible counterexamples) has output a YES, because it has not yet found a counterexample, we cannot be sure that that is its result. We only think that that is its result. It can always “change its mind”. We know that its last output is correct but, at any given moment at which YES is its output, we do not know that YES will be its last output. Trial and error procedures have been quite widely used to model the cog- nitive process of induction (Angluin & Smith, 1983) and particularly gram- matical induction (Osherson, Stob & Weinstein, 1986; Pinker, 1979). They are one type of uncomputable procedure that we can run on a computer. But there are others, and other cognitive processes besides induction, that they can be used to model.

3. “Geographies” of the mind and of the uncomputable
I want to suggest several ways that parts of thinking might be modelled by uncomputable processes. To do this, I will pluck ideas from the mathematical theory of the uncomputable and set them down in various parts of the mind. To try to give some order to this process, let me sketch “geographies” of the two territories involved-f the mind, where the ideas will sit, and of the theory of the uncomputable from which they will come.

1. An input processor that takes information from the sensors-say a pat- tern on the retina-and turns it into a form that the central processor can deal with. For example, it might take a visual signal and turn it into the message: THIS IS A SABRE-TOOTHED TIGER.
2. A central processor that takes the results produced by the input proces- sor and turns them into messages for the output processor. For example, it might take the message: THIS IS A SABRE-TOOTHED TIGER and turn it into the message: RUN.
3. An output processor that takes the results of the central processor and turns them into something that can be used to affect the world. For example, it might take the message RUN and turn it into messages to control specific muscles to remove us from the immediate area.

4. A program selector that selects a suitable program from the set of all available programs. It might, for example, study the situation and decide that it was time to use the ANIMAL RECOGNIZING PROGRAM rather than the BEAUTY APPRECIATION PROGRAM.

Example of a real-life application in an existing uncomputable AI project:

Facebook chatbot ai project is still an ongoing issue, that does'nt come to an end.