【免费】OnComputableNumbers,withanApplicationtotheEntscheidungsproblem

需积分: 0 31 浏览量更新于2023-05-21 评论 1 收藏 935KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

On Computable Numbers, with an Application to the

Entscheidungsproblem

(Proc. Lond. Math. Soc., ser. 2 vol. 42 (1936–37), pp. 230–265)

– A Correction

(ibid. vol. 43 (1937), pp. 544–546)

Christos Papadimitriou on —

ALAN AND I

During my sad college years, I often dreamed of Alan. At the time I did not know it was Alan

Turing that I was dreaming of, but it was. I was studying a subject that did not excite me (electrical

engineering), in the inﬂexible educational system of an oppressive society (Greece of the colonels).

I had no access to a proper scientiﬁc library. My life as a ﬂedgling scientist was one of frustration,

blind longing, and episodes of false epiphany. A few subjects (systems theory, communication the-

ory), even though they were taught at school in the most mundane way, enabled one to imagine a

courageous intellectual universe in which questions of the most fundamental nature are confronted

rigorously and head on, and I was aching to enter that universe.

I don’t remember when, in which outdated textbook, handed to me by whom, I got my ﬁrst

glimpse of the Turing machine. I did not get it all at once, but I knew immediately that this abstract

device is an important exemplar of the higher sphere I had been dreaming. I looked up in the

dictionary the verb ‘to ture’ (I really did). I sought more information, every book I opened those

days I opened it on the index page where ‘Turing machine’ should be.

Eventually I did put it all together, how a British mathematician named Alan Turing answered

through his machine the world’s most fundamental question, ‘what can be computed?’ and did so

with amazing rigor, elegance, imagination and economy. But those days I was thinking of the Turing

machine as a singular breakthrough, the end of a story, something of the past. Two years later, in

1973 – after a year in the Greek army that was even bleaker than my tertiary studies – I was fortunate

to ﬁnd myself at Princeton (Turing’s Princeton, by the way, where I lived for a year in room 2B of

the Graduate College rumored to be Alan’s room 35 years before). At Princeton I was introduced

to the Theory of Computation, the rich and vibrant scientiﬁc tradition essentially built on Turing’s

formalism. I remember how grateful I felt that my prayers had been answered, so to speak, and I was

ﬁnally entering the realm of my dreams, far more elegant and exciting than I could ever imagine.

And 5 years later, whilst teaching at Harvard with my friend Harry Lewis, we wrote a textbook on

the subject.

But even though my life now revolved around his intellectual heritage, the truth is, I did not

know Alan. I understood next to nothing about the man’s life, personality, and breadth of achieve-

ment. In 1983, 2 years after our textbook was published, I read one of the books that have inﬂuenced

me most: Turing’s powerful and deﬁnitive biography by Andrew Hodges. Alan became my hero,

a giant and relentless intellect, a fascinating and complex personality, a man of immense accom-

plishment, impact, and tragedy. When, more than a decade later, the second edition of our textbook

14 Part I

was published, Harry and I decided that we must have Alan Turing’s image on the cover. Since

the mid-1980s, every time I teach about Turing machines and undecidability, I stop to tell the class

about Alan, about his ingenious work and about his tragic end. Once in a while I teach a course at

Berkeley on ‘Reading the Classics’, and in it we spend a month on Turing, because I believe that

every graduate student should be exposed directly to the exacting self-conscious greatness of Alan’s

opus.

There is a scene in Gibson’s Neuromancer, at the very end of Part Three, where the hero returns

to his hotel room to ﬁnd it full of cops. ‘Turing’, they tell him. ‘You are under arrest’. They mean

‘Turing police’, a ﬁctional force bent on rooting out AI from the planet, but it does not matter, for

me this line, read literally, contained the germ of an idea: What if Alan Turing were alive and turned

up some place, unbidden? This strange fantasy lived inside me for a few years.

Turing is not my only intellectual hero. In poetry, my hero is Constantine Cavafy, a Greek

from Alexandria who died when Alan Turing was 21. He wrote some of the greatest poems of the

twentieth century, a stunning opus sharply divided between subtle historical metaphor and rather

unsubtle eroticism. (I do not know why both my heroes happen to be homosexuals.) In 1997 I was

in Greece, and I went to see a ﬁlm titled Cavafy. I liked it so-so, but I remember coming out of the

theatre impressed by the director’s gesture: to honor one’s hero by creating a work of art bearing his

name. And then, right there in the theatre lobby, I had a vision: there was a blue paperback hovering

above, and the title in front read Turing (A Novel).

Writing a novel had never occurred to me before. I had never written short stories or poetry. I

had of course noticed over the years that writing was not my weakest point, and neither was it for

me the hated chore that comes after research, as it was for many of my colleagues. That night I

thought about a plot.

This was 1997, when it was slowly becoming apparent to many computer scientists that the true

object of our science is not the computer, but the Internet (by which I mean both the network of

networks and the World Wide Web). In a sense, the Internet is the ultimate legacy of Alan Turing.

The reason it spread like wildﬁre ever since a physicist named Tim Burners-Lee invented ‘click’

in 1989 is because there were millions of computers on the desks of people at that time, and these

computers were all universal and so, in addition to everything else, they could be easily made to

click. But universality was a minority opinion among computer dreamers during the 1930s and

1940s. By making his universal machine so compelling, Turing inﬂuenced deeply von Neumann

and the way computers turned out to be. Universality and software would have probably taken root

at some point in computers no matter what, but we can only speculate about the setbacks and delays

this would have required without Turing.

But why did Turing envision universality? The reason is, he did not set out just to answer the

question ‘What can (and what cannot) be computed?’ per se, as I inaccurately mentioned above.

If he had only wanted to establish the existence of unsolvable problems, Turing could just use

diagonalisation or growth, and the universal Turing machine might never come to light. Fortunately,

he wanted to do something more ambitious and speciﬁc – and central to the scientiﬁc agenda of the

time – he wanted to show that the Entscheidungsproblem (the decision problem for sentences not of

arithmetic, but even of ﬁrst-order logic) cannot be solved by computers. In other words, his goal was

to sharpen G

odel’s negative result, to extinguish the last glimmer of hope left by the Incompleteness

Theorem. And to accomplish this he needed the universal Turing machine.

The night after I saw that movie, all this was in my mind. If, through this long chain of logic,

the Internet is Alan’s ultimate creation, why would not the Internet return the favor, and bring its

creator back to life? The thought did not let me sleep. The Internet does confer a lame kind of

immortality (just search for ‘Alan Turing’ on the web). Imagining a more explicit form, an Inter-

net spirit residing somewhere and everywhere, a kind of impromptu, hacked-up SETI, was only a

16 Part I

ON COMPUTABLE NUMBERS, WITH AN

APPLICATION TO THE ENTSCHEIDUNGSPROBLEM

By A. M. TURING

[Received 28 May, 1936.—Read 12 November, 1936.]

The “computable” numbers may be described brieﬂy as the real numbers whose expressions

as a decimal are calculable by ﬁnite means. Although the subject of this paper is ostensibly the

computable numbers, it is almost equally easy to deﬁne and investigate computable functions of an

integral variable or a real or computable variable, computable predicates, and so forth. The funda-

mental problems involved are, however, the same in each case, and I have chosen the computable

numbers for explicit treatment as involving the least cumbrous technique. I hope shortly to give an

account of the relations of the computable numbers, functions, and so forth to one another. This will

include a development of the theory of functions of a real variable expressed in terms of computable

numbers. According to my deﬁnition, a number is computable if its decimal can be written down

by a machine.

In §§9,10 I give some arguments with the intention of showing that the computable numbers

include all numbers which could naturally be regarded as computable. In particular, I show that

certain large classes of numbers are computable. They include, for instance, the real parts of all

algebraic numbers, the real parts of the zeros of the Bessel functions, the numbers π, e, etc. The

computable numbers do not, however, include all deﬁnable numbers, and an example is given of a

deﬁnable number which is not computable.

Although the class of computable numbers is so great, and in many ways similar to the class

of real numbers, it is nevertheless enumerable. In §8 I examine certain arguments which would

seem to prove the contrary. By the correct application of one of these arguments, conclusions are

reached which are superﬁcially similar to those of G

odel

. These results have valuable applications.

In particular, it is shown (§11) that the Hilbertian Entseheidungsproblem can have no solution.

In a recent paper Alonzo Church

has introduced an idea of “effective calculability”, which

is equivalent to my “computability”, but is very differently deﬁned. Church also reaches similar

conclusions about the Entseheidungsproblem

. The proof of equivalence between “computability”

and “effective calculability” is outlined in an appendix to the present paper.

1. Computing machines

We have said that the computable numbers are those whose decimals are calculable by ﬁnite means.

This requires rather more explicit deﬁnition. No real attempt will be made to justify the deﬁnitions

given until we reach §9. For the present I shall only say that the justiﬁcation lies in the fact that the

human memory is necessarily limited.

odel, “

Uber formal unentscheidbaro S

atze der Principia Mathematica und ver-wandter Systeme, I”, Monatshefte

Math. Phys., 38 (1931), 173–198.

Alonzo Church “An unsolvable problem of elementary number theory”, American J. of Math., 58 (1936), 345–363.

Alonzo Church “A note on the Entseheidungsproblem”, J. of Symbolic Logic, 1 (1936), 40–41.

On Computable Numbers, with an Application to the Entscheidungsproblem 17

We may compare a man in the process of computing a real number to a machine which is only

capable of a ﬁnite number of conditions q

, q

, ..., q

, which will be called “m-conﬁgurations”.

The machine is supplied with a “tape” (the analogue of paper) running through it, and divided into

sections (called “squares”) each capable of bearing a “symbol”. At any moment there is just one

square, say the r-th, bearing the symbol S(r) which is “in the machine”. We may call this square

the “scanned square”. The symbol on the scanned square may be called the “scanned symbol”. The

“scanned symbol” is the only one of which the machine is, so to speak, “directly aware”. However,

by altering its m-conﬁguration the machine can effectively remember some of the symbols which

it has “seen” (scanned) previously. The possible behaviour of the machine at any moment is deter-

mined by the m-conﬁguration q

and the scanned symbol S(r). This pair q

, S(r) will be called the

“conﬁguration”: thus the conﬁguration determines the possible behaviour of the machine. In some

of the conﬁgurations in which the scanned square is blank (i.e. bears no symbol) the machine writes

down a new symbol on the scanned square: in other conﬁgurations it erases the scanned symbol.

The machine may also change the square which is being scanned, but only by shifting it one place

to right or left. In addition to any of these operations the m-conﬁguration may be changed. Some of

the symbols written down will form the sequence of ﬁgures which is the decimal of the real number

which is being computed. The others are just rough notes to “assist the memory”. It will only be

these rough notes which will be liable to erasure.

It is my contention that these operations include all those which are used in the computation of

a number. The defence of this contention will be easier when the theory of the machines is familiar

to the reader. In the next section I therefore proceed with the development of the theory and assume

that it is understood what is meant by “machine”, “tape”, scanned”, etc.

2. Deﬁnitions

Automatic machines

If at each stage the motion of a machine (in the sense of §1) is completely determined by the

conﬁguration, we shall call the machine an “automatic machine” (or a-machine).

For some purposes we might use machines (choice machines or c-machines) whose motion is

only partially determined by the conﬁguration (hence the use of the word “possible” in §1). When

such a machine reaches one of these ambiguous conﬁgurations, it cannot go on until some arbitrary

choice has been made by an external operator. This would be the case if we were using machines to

deal with axiomatic systems. In this paper I deal only with automatic machines, and will therefore

often omit the preﬁx a-.

Computing machines

If an a-machine prints two kinds of symbols, of which the ﬁrst kind (called ﬁgures) consists entirely

of 0 and 1 (the others being called symbols of the second kind), then the machine will be called a

computing machine. If the machine is supplied with a blank tape and set in motion, starting from

the correct initial m-conﬁguration, the subsequence of the symbols printed by it which are of the

ﬁrst kind will be called the sequence computed by the machine. The real number whose expression

as a binary decimal is obtained by prefacing this sequence by a decimal point is called the number

computed by the machine.

At any stage of the motion of the machine, the number of the scanned square, the complete

sequence of all symbols on the tape, and the m-conﬁguration will be said to describe the complete

conﬁguration at that stage. The changes of the machine and tape between successive complete

conﬁgurations will be called the moves of the machine.

剩余102页未读，继续阅读

八烨

粉丝: 1
资源: 4

会员权益专享

On Computable Numbers, with an Application to the Entscheidungsp...

评论0

会员权益专享

最新资源

On Computable Numbers, with an Application to the Entscheidungsp...

评论0

ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM

计算机英文文献及译文

intelligent-machinery-a-heretical-theory--1951 - 副本1

1936 年 11 月 12 日，艾伦·图灵（Alan Turing） 发表了题为 On Computable Numbers with an Application to the Entscheidungs-problem 的论文，定义了一种“通用机器”的概念，由一个虚拟的机器替代人类进行数学运算。 这个概念如今被称为什么？

alibaba java coding guidelines idea inside write-action

接口Computable的使用方法

error: divide() in Complex cannot implement divide() in Computable private void divide(){ ^ attempting to assign weaker access privileges; was public

error: divide() in Complex cannot implement divide() in Computable void divide(){ ^ attempting to assign weaker access privileges; was public

设计一个Circle类来扩展GeometricObject，并实现接Computable。

定义一个接口computable，该接口含有两个方法computeArea和computeLong。 定义实现该接口的类Circle，其中circle类包含一个成员变量，即半径radius，此外该类还要重写computeArea方法计算圆的面积，重写computeLong方法计算圆的周长。

设计一个接口Computable，该接口中包括： •常量PI=3.14，可以用于计算圆的面积

interface Computable <T> { T add(T obj); T substract(T obj); T multiply(T obj); T divide(T obj); }

cge用stata软件能做吗

cge模型基于碳排放

会员权益专享

最新资源

1936 年 11 月 12 日，艾伦·图灵（Alan Turing）发表了题为 On Computable Numbers with an Application to the Entscheidungs-problem 的论文，定义了一种“通用机器”的概念，由一个虚拟的机器替代人类进行数学运算。这个概念如今被称为什么？

定义一个接口computable，该接口含有两个方法computeArea和computeLong。定义实现该接口的类Circle，其中circle类包含一个成员变量，即半径radius，此外该类还要重写computeArea方法计算圆的面积，重写computeLong方法计算圆的周长。