31 Dec
2023
31 Dec
'23
10:30 p.m.
But a Turing machine that is connected to the WWW is an oracle machine:
MN> Yes, Turing describes NON-algorithmic machines (like the oracle machine—the
o-machine as he called it)—but so far we are stuck in the algorithmic.
The following article has a good readable historical development of the issues. (The word
'readable' means that if you had studied some of these topics many years ago and
forgot almost everything, the article has enough clear discussion that you don't need
to do any further studying elsewhere. If you remember a little more, you can flip through
quite fast. That is not something you can say about most publications on these topics.)
Turing Oracle Machines, Online Computing, and Three Displacements in Computability Theory
Robert I. Soare, http://www.people.cs.uchicago.edu/~soare/History/turing.pdf
Following is the final paragraph on p. 60:
Conclusion 14.4. For pedagogical reasons with beginning students it is
reasonable to first present Turing a-machines and ordinary computability.
However, any introductory computability book should then present as soon
as possible Turing oracle machines (o-machines) and relative computability.
Parallels should be drawn with offline and online computing in the real world
John
----------------------------------------
From: "Nadin, Mihai" <nadin(a)utdallas.edu>
There is NO general intelligence—good for everything; rather concrete intelligence, as the
context defines its characteristics.
I hope that these notes explain my invitation to my respected colleagues to read Hilbert’s
challenge and Turing’s paper. Yes, Turing describes NON-algorithmic machines (like the
oracle machine—the o-machine as he called it)—but so far we are stuck in the algorithmic.
Best wishes for a happy and healthy 2024
Mihai Nadin