The human soul may just be an extremely complex algorithm of a Turing machine.
Author | Lawrence C. Paulson
Compilation | Edited by Wang Yue | Chen Caixian
In October 1950, a paper titled “Can Machines Think?” appeared. In this paper, a very thought-provoking test is proposed, that is, when the tester is separated from the testee (a real person and a machine), the testee is asked random questions through a communication device, and the tester is asked. The testers guessed whether the person they were talking to was a real person or a machine.
After multiple tests, if the machine could, on average, get each participant to make more than 30 percent false positives, the machine passed the test and was deemed to have human intelligence.
The first time people realized that robots might have human intelligence began there. This test is the Turing test that millions of sci-fi fans are talking about. This article also earned the author Alan Turing the title of “Father of Artificial Intelligence”.
The road to artificial intelligence, or the source of the history of computer development, is a paper published by Turing at the age of 24. In this paper, he gave a strict mathematical definition of “computability” and proposed the famous “Turing Machine” assumption. A Turing machine is not a specific machine, but a mental model that can create a very simple but extremely powerful computing device for computing all conceivable computable functions.
Because Turing invented the Turing machine, people jumped out from time to time to claim that Turing actually “invented the computer”. However, Turing machines are not the same design as actual computing machines. A Turing machine is not even an abstract model of a machine. It turns out (as evidenced by Turing’s remarks) that a Turing machine is a model of a person writing on paper on a table. So, why did Turing invent the Turing machine, and where will the Turing machine lead us?
1
Turing’s paper “On Computable Numbers”
The best way to answer these questions is to put the textbook aside and open the paper. Today, borrowing a 1936 journal doesn’t require filling out a borrowing card or waiting an hour for a librarian to pick it up from the library, all we need is a glass of malt whisky and easy access to Google at home. The Turing paper we are looking for is as follows:
Paper address: https://ift.tt/zQAoN87
There are some mistakes in the paper, but the flaws do not hide the flaws. As Joel David Hamkins said, Turing defined computable real numbers as having a computable decimal expansion, which doesn’t actually work, but it’s not difficult to fix.
Turing stated the intention of writing this paper in the title: “On Computable Numbers and Their Application to the “Decision Problem”. The “Entscheidungsproblem (Decision Problem)” asks whether there is an efficient technique to decide a given The given first-order logic formula is valid, that is, true in all interpretations.
Turing unfolded his idea as follows:
We can compare a person who is calculating real numbers to a machine that can only satisfy a finite number of conditions q1, q2, … qR…. There is a long “paper tape” running through the machine, and the paper tape is divided into many parts, which we call squares, and each square can carry a “symbol” …some of the written symbols form the decimal sequence of digits of the real numbers being calculated, while others are just rough notes to “help memorize”. These sketchy notes can be erased. My argument is that this way of swiping around on a tape, swiping to a symbol and doing something with that symbol, includes all the operations that are used for numerical calculations.
…
A “computable number” is simply a real number whose decimal representation is computable by limited means. By my definition, a number is computable if its decimal representation can be written down by a machine.
Turing then defines and proves that this is a typical mathematical paper, not a typical engineering paper, in which the reader wants to see a discussion of how to implement one of the mechanisms described in the paper. As we can see from Turing’s title and article, Turing’s main concern is the computation of a real number to infinite decimal places.
There are many other important contributions of this paper:
-
Universal Turing Machines, and the idea of coding machines in digital form
-
The halting problem of such a coded machine, and the undecidability of diagonalization
After writing this paper, Turing opened the door to the field of theoretical computing science.
2
Universal Turing Machine
We can’t be sure what gave Turing the idea of a Universal Turing Machine (UTM), but once he did, he might think the existence of a Universal Turing Machine was obvious. Since the purpose of a Turing machine is to simulate a clerk working at a desk, and a Turing machine operates like a clerk—performing this or that operation according to a given list of transition rules, depending on the machine state and tape symbol—obviously requires A Turing machine to perform such routine tasks. Turing’s paper is a bit sketchy about the details of the construction, but no one seems to mind.
Today, we have universal Turing machines that have been designed to the fullest. Decades ago, at the University of Cambridge, Dr. Ken Moody wrote a generic Minsky registrar:
Link: https://ift.tt/szAejOi
Such machines have finite registers, each of which can store arbitrarily large non-negative integers. It has a finite program consisting of three different types of marked instructions:
-
Increment register R and jump to label L , or R +→ L
-
Test/decrement register R and jump to label L 0/ L 1, or L 0↞R−→ L 1
-
interrupt.
Such machines are easier to program than Turing machines, although they still don’t look like real computers.
Moody uses a standard bijection between N and N×N , packing a list of integers into a single integer. He wrote a small library of small register machines to do things like stack pushes and pops from the stack, and created a design that was reminiscent of the fetch-execute cycle of a real processor. The whole process can be seen in the following slides. The picture below is the machine itself:
The figure below shows the overall structure of the machine. (The authors of both figures are Andrew Pitts, professor of theoretical computing science at the University of Cambridge.)
Surprisingly, the structure of this machine is really simple!
3
downtime problem
The pause problem is clearly undecidable. Otherwise, many mathematical conjectures will be difficult to solve, such as Fermat’s last theorem: just write a program to search for x, y, z, n>2, such that 
, and asks if it terminates. However, the undecidability of halting must be rigorously expressed and proven.
Contrary to popular belief, Turing’s paper does not discuss the halting problem, but a property related to the halting problem, which he calls “circularity.” A Turing machine is cyclic if it “writes down only a finite number of symbols of the first kind” (i.e. 0s and 1s). I think that circularity is important because Turing was particularly fond of approximating real numbers as infinite binary strings. Physicist Christopher Strachey claimed in a 1965 letter to Computer Journal that Turing gave him a proof of the undecidability of the halting problem.
4
Turing and Maurice Wilkes
In September 2009, David P. Anderson interviewed Maurice Wilkes, who had the opposite view of Turing:
David P. Anderson: What do you think is the importance of Turing’s 1936 paper on decision problems?
Maurice Wilkes: I think an engineer would take the idea of a stored program as an important theory like the Trinity, and would say, “This is absolutely top-notch, and that’s how it should be done.”
The ideas in that paper are not in any meaningful way different from what I say. He’s been lucky enough to publish that paper, I mean Alonzo Church got the same result in other ways.
Article address: https://ift.tt/lvUGgsO
It should be noted that at the time of the interview, Maurice Wilkes was 96 years old, and he himself is a famous computer pioneer, the father of EDSAC (Electronic Delay Storage Automatic Calculator). His envy of Turing’s lofty status can be seen in this bizarre answer. The two obviously don’t get along! We also saw Maurice Wilkes’ disdain for theory: while coding machines as numbers was to be expected of a stored-program computer, Turing’s work was pure mathematics without any engineering significance. Turing was interested in practical computer engineering, but he repeatedly tried to get involved in real engineering, but was repeatedly frustrated.
And what about those remarks about Church?
5
Turing and Church at Princeton
When Turing was doing research, many researchers focused on the idea of ”efficient computability.” Here I refer readers to Church’s “An Unsolvable Problem in Elementary Number Theory” (see figure below).
Paper link: https://ift.tt/8Ruirw9
Honestly, this paper is a tough read, but it gets us there. This paper gives a definition of a λ-calculus, a definition of a recursive function (in the Kleene/Gödel sense), and some incomprehensibility of the existence and equivalence of paradigms in λ-calculus judgement result. Church and Kleney have proved the equivalence of λ-definable and recursive functions; while Turing was at Princeton, the equivalence between λ-definable and Turing-computable functions was also proved , so we have the Church-Turing thesis, which refers to the fact that efficiently computable functions are precisely those in the mathematical equivalence class.
6
Is the Church-Turing thesis correct?
As is often said, we can’t prove this thesis right because “effectively computable” is not an exact concept. We can think of Turing computable functions as a fairly inclusive class, since it includes many functions that cannot be computed during the lifetime of the universe. With the help of the Ackermann function, we can easily get the paradigm.
The modern form of the Ackermann function is as follows:
Article link: https://ift.tt/oAPnXiw
If you define f(n)=A(n,n), you cannot expect to compute even f(4). g(n)=A(4,n) is almost impossible to compute despite being primitive recursion.
Although there were no digital computers until the 1930s, the concept of efficient computability was well known to mathematicians. The concept of validity has long appeared in the rectilinear and compass structures of Greek geometry, and validity is also an integral part of the judgment problem and Hilbert’s tenth problem. Compared to Gödel’s recursive functions and Church’s lambda calculus, the genius of Turing’s concept is that it is clearly correct. Gödel himself is not sure whether his recursive function captures the idea of computation, nor is it clear that Church had the right idea. Only Turing’s idea is simple and natural. Turing’s ideas are provably equivalent to other models and provide a rationale for all of them. He pointed out this fact in his 1937 paper “Computability and λ-Definability”.
The purpose of this paper is to show that the computable functions proposed by the authors are identical to Church’s λ-definable functions and the general recursive functions proposed by Erbran and Gödel and developed by Kleine. These same functions prove that every X-definition function is computable, and every computable function is generally recursive.
Note that Turing wrote “computable”, and we’re going to write “Turing computable”.
Original link:
https://ift.tt/M6EPHGe For more content, click below to follow: Scan the code to add AI technology review WeChat account, contribute & join the group: 
Leifeng Network
This article is reprinted from: https://www.leiphone.com/category/academic/0GSv6WDPHsXnMC6o.html
This site is for inclusion only, and the copyright belongs to the original author.