不可計(jì)算理論

1、不可計(jì)算理論 計(jì)算機(jī)有著強(qiáng)大的計(jì)算能力，那是不是當(dāng)計(jì)算機(jī)的計(jì)算能力達(dá)到極高水平時(shí)就可以解決所有問題呢？要回答這個(gè)問題，首先我們得明確計(jì)算機(jī)所能做的事計(jì)算。什么是計(jì)算呢？直觀地看，計(jì)算一般是指運(yùn)用事先規(guī)定的規(guī)則，將一組數(shù)值變換為另一（所需的）數(shù)值的過程。對某一類問題，如果能找到一組確定的規(guī)則，按這組規(guī)則，當(dāng)給出這類問題中的任一具體問題后，就可以完全機(jī)械地在有限步內(nèi)求出結(jié)果，則說這類問題是可計(jì)算的。這種規(guī)則就是算法，這類可計(jì)算問題也可稱之為存在算法的問題。這就是直觀上的能行可計(jì)算或算法可計(jì)算的概念。在20世紀(jì)以前，人們普遍認(rèn)為，所有的問題類都是有算法的，人們的計(jì)算研究就是找出算法來。但是20世紀(jì)初

2、，人們發(fā)現(xiàn)有許多問題已經(jīng)過長期研究，卻仍然找不到算法。于是人們開始懷疑，是否對這些問題來說，根本就不存在算法，即它們是不可計(jì)算的。這種不存在性當(dāng)然需要證明，這時(shí)人們才發(fā)現(xiàn)，無論對算法還是對可計(jì)算性，都沒有精確的定義！按前述對直觀的可計(jì)算性的陳述，根本無法作出不存在算法的證明，因?yàn)椤巴耆珯C(jī)械地”指什么？“確定的規(guī)則”又指什么？仍然是不明確的。 解決問題的需要促使人們不斷作出探索。1934年，哥德爾提出了一般遞歸函數(shù)的概念，并指出：凡算法可計(jì)算函數(shù)都是一般遞歸函數(shù)，反之亦然。同年，丘奇證明了他提出的可定義函數(shù)與一般遞歸函數(shù)是等價(jià)的，并提出算法可計(jì)算函數(shù)等同于一般遞歸函數(shù)或可定義函數(shù)，這就是著名的“

3、丘奇論點(diǎn)”。用一般遞歸函數(shù)雖給出了可計(jì)算函數(shù)的嚴(yán)格數(shù)學(xué)定義，但在具體的計(jì)算過程中，就某一步運(yùn)算而言，選用什么初始函數(shù)和基本運(yùn)算仍有不確定性。為消除所有的不確定性，圖靈在他的“論可計(jì)算數(shù)及其在判定問題中的應(yīng)用”一文中從一個(gè)全新的角度定義了可計(jì)算函數(shù)。他全面分析了人的計(jì)算過程，把計(jì)算歸結(jié)為最簡單、最基本、最確定的操作動(dòng)作，從而用一種簡單的方法來描述那種直觀上具有機(jī)械性的基本計(jì)算程序，使任何機(jī)械(能行)的程序都可以歸約為這些動(dòng)作。這種簡單的方法是以一個(gè)抽象自動(dòng)機(jī)概念為基礎(chǔ)的，其結(jié)果是：算法可計(jì)算函數(shù)就是這種自動(dòng)機(jī)能計(jì)算的函數(shù)。這不僅給計(jì)算下了一個(gè)完全確定的定義，而且第一次把計(jì)算和自動(dòng)機(jī)聯(lián)系起來，對后

4、世產(chǎn)生了巨大的影響，這種“自動(dòng)機(jī)”后來被人們稱為“圖靈機(jī)”。圖靈機(jī)有一條無限長的紙帶，紙帶被分成若干小方格方格內(nèi)可以是一個(gè)符號(hào)，也可以是空白，除此之外還有一個(gè)有限狀態(tài)控制器。紙帶起著存儲(chǔ)器的作用，控制器上的讀寫頭可以在帶上左右移動(dòng)，而讀寫頭可以根據(jù)當(dāng)前狀態(tài)和看到的方格內(nèi)的符號(hào)，采取下列三種行動(dòng)之一：左移一格，右移一格，或者靜止不動(dòng)，具體采取哪一種行動(dòng)應(yīng)根據(jù)該圖靈機(jī)的控制規(guī)則。或者可以從另一個(gè)角度來理解，由于讀寫頭每次只對應(yīng)一個(gè)小方格且它本身具有一定的狀態(tài)，比如接受，拒絕或進(jìn)入循環(huán)。當(dāng)其進(jìn)入接受或者拒絕狀態(tài)時(shí)，就會(huì)發(fā)生停機(jī)（停機(jī)問題），即讀寫頭不再操作，不會(huì)再產(chǎn)生新的格局；如果其一直處于循環(huán)狀態(tài)

5、，將一直產(chǎn)生新的格局。針對讀寫頭的兩種狀態(tài)，可以看出：有一類圖靈機(jī)，它們對任何輸入都會(huì)停機(jī)（要么接受，要么拒絕）。這類圖靈機(jī)又被稱為判定器，被判定器識(shí)別的語言叫做可判定語言。那么，是否存在一個(gè)不可判定語言（不存在一個(gè)圖靈機(jī)可以判定該語言）呢？答案是肯定的，并不是所有的語言都可以被判定。下面簡短的證明一下。假設(shè)一個(gè)語言A = (<M>,) | <M>是表示圖靈機(jī)M的字符串，是一個(gè)字符串。M接受。即語言A中的字符串都有兩部分組成：第一部分是一個(gè)圖靈機(jī)M的字符串表示<M>；第二部分是一個(gè)字符串，且M接受。假設(shè)語言A是可判定的，也就是存在一個(gè)判定器H。當(dāng)M接受時(shí)，H

6、接受(<M>,)；當(dāng)M不接受時(shí)，H拒絕(<M>,)。 （注意H是一個(gè)判定器，它總會(huì)停機(jī)，接受或拒絕(<M>,)）。那么我們對H稍加改造，將它的結(jié)果取一下反：當(dāng)M接受時(shí)，H拒絕 (<M>,)；當(dāng)M不接受時(shí)，H接受(<M>,)。這很容易，只要把H的接收狀態(tài)和拒絕狀態(tài)互換一下身份即可。但是若把H自己的序列化字符串<H>提供給H會(huì)發(fā)生什么？可以看出，當(dāng)H接受<H>時(shí)，H拒絕<H>；當(dāng)H不接受<H>時(shí)，H接受<H>。在此導(dǎo)出了矛盾，從而唯一的結(jié)論只能是，假設(shè)的H是不可能存在的。對于這種

7、不可判定的語言，是無法構(gòu)造出一個(gè)圖靈機(jī)來接受或拒絕該字符串的。一個(gè)不可判定的語言，就是一個(gè)不可計(jì)算的問題，不可計(jì)算問題就是超出了計(jì)算能力的問題，不能被任何有步驟的，確定性的算法所能解決的問題。在如上圖靈機(jī)的例子中我們可以把有限狀態(tài)讀寫頭看作是機(jī)器的程序執(zhí)行代碼，而存儲(chǔ)帶上存的只是被處理的數(shù)據(jù)。圖靈在描述他的另一個(gè)機(jī)器模型通用機(jī)器時(shí)還提出了可以把有限狀態(tài)指令也存放在存儲(chǔ)帶上，讓讀寫頭根據(jù)讀入的指令進(jìn)行下一步操作。可以證明這樣存儲(chǔ)有指令的通用圖靈機(jī)能夠?qū)崿F(xiàn)任何一個(gè)圖靈機(jī)，也就是說可以解決任意一個(gè)圖靈可計(jì)算問題?，F(xiàn)在我們廣泛使用的計(jì)算機(jī)的確就是采用了存儲(chǔ)指令這一原理因而可以解決“萬能”計(jì)算問題的。具

8、體實(shí)現(xiàn)方法是：對于需要解決的問題用軟件編制程序，再把程序和數(shù)據(jù)都存放在同一個(gè)存儲(chǔ)器（內(nèi)存）里，由中央處理器（CPU）根據(jù)指令對數(shù)據(jù)進(jìn)行操作。這樣的機(jī)器也叫做“存儲(chǔ)程序計(jì)算機(jī)”。在為第一臺(tái)存儲(chǔ)程序計(jì)算機(jī)研發(fā)計(jì)劃做顧問時(shí)，約翰·馮·諾伊曼寫了一個(gè)草案報(bào)告描述了這種帶有中央處理器、內(nèi)存、I/O、總線的存儲(chǔ)程序計(jì)算機(jī)。因此可以說我們今天使用的存儲(chǔ)程序計(jì)算機(jī)就是圖靈機(jī)理論的實(shí)現(xiàn)。 圖靈機(jī)的概念有十分獨(dú)特的意義：如果把圖靈機(jī)的內(nèi)部狀態(tài)解釋為指令，用字母表的字來表示，與輸出字輸入字同樣存貯在機(jī)器里，那就成為電子計(jì)算機(jī)了。由此開創(chuàng)了“自動(dòng)機(jī)”這一學(xué)科分支，促進(jìn)了電子計(jì)算機(jī)的研制工作。圖靈機(jī)

9、模型幫助我們了解了計(jì)算機(jī)的工作，因而我們能說“計(jì)算機(jī)并不能解決所有問題”，例如停機(jī)問題。我們也可以構(gòu)造出其他不可判定的問題，這些問題是計(jì)算機(jī)不能解決的，也就是說有不可能存在的程序Programs That Never ExistIts clear and explicit that various programs which can do many things in our daily life. They do everything based on clear, explicit and valid instructions that has been given to them by

10、 the programmers in advance to deal with different circumstances.But, can computer do everything that is explicit and clear? The answer is NO.SIMPLE FACTSWe are attempting to prove that the answer is NO, which is absolute, starting from some obvious facts that is beyond doubt.1. Computers always do

11、things based on the instructions given.2. All programs has to obey logical rules, or they will never really exist.3. Proof by contradiction is valid. That is, if A is true lead to the fact that B is also true, and we know exactly B cannot be true, we can conclude that A is false.4. Computer programs

12、 can accept any type of input if that is within the range of the ability given, even the programs themselves.EXAMPLE1 “AlwaysYes.exe”Before giving the first typical example, a kind of boring programs should be mentioned first. They are called YES-NO programs, that is, they accept all kinds of input,

13、 and can judge whether the input follows the rules, with the only two kinds of output: “YES” & “NO”. If an unexpected input cannot be judged, the output will be “NO” again.For example, one program (Suppose it is called “isPhoto.exe”) (Suffix “.exe” is used here just to represent it is an executa

14、ble program, which is taken from Microsoft Windows) is meant to tell whether the input is a photo (Photos should end with “.png”, .or “.jpg”, etc. In that case, if “1.png” is the input, the program will give the output “YES”, and “a.exe” will result in “NO”. Another example is “isFileNameLengthPosit

15、ive.exe”, which return whether the length of the name is positive (greater than zero), which is always TRUE. So, exactly we will always get the output “YES” whatever we use as input.So, we are attempting to create a program that is used to detect whether a program is always giving “YES” under any ci

16、rcumstances. We can call it “AlwaysYes.exe”. That is, meaningful input of the program has to be programs, otherwise, youll only get a “NO”. If one program is always giving “YES” as the output (like the “isFileNameLengthPositive.exe” mentioned above), then “AlwaysYes.exe” will give the output “YES”,

17、otherwise, “NO”.So, we are going to prove, this kind of program cannot be created. We can use the method, proof with contradiction to prove that, this kind of program never exist, which seems incredible.Suppose we can REALLY make out such a program. In that case, we are capable of doing an easier th

18、ing, that is, we can make out a program, namely “YesOnSelf.exe”. The new program only do such things: check whether the output of the input program (the program to be tested) is “YES” if the input of the input program is the input program itself. For instance, if we take “isPhoto.exe” as the input o

19、f “YesOnSelf.exe”, the output will be “NO”, since “isPhoto.exe” is not a photo and it will result in the fact that the output of “isPhoto.exe” is “NO”, and result in the fact that the output of “YesOnSelf.exe” is “NO”. We can see clearly that “YesOnSelf.exe” can do only a little part of what “Always

20、Yes.exe” can do.So, here comes the big problem. What will happen if we run “YesOnSelf.exe” on itself?Luckily, we only have two probable answers, so we can consider each one in turn. If the output is “YES”, we know that (according to the denition of “YesOnSelf.exe”), “YesOnSelf.exe” should output “YE

21、S” when run on itself. But what if the output of “YesOnSelf.exe” when run on itself happened to be “NO”? Well, it would mean that (again, according to the denition of “YesOnSelf.exe”) “YesOnSelf.exe” should output “NO” when run on itself. Again, this statement is perfectly consistent. It seems like

22、“YesOnSelf.exe” can actually choose what its output should be. This is not practical when dealing with programs, since we cannot figure out what computers are going to do.What is more interesting is that we can create a program named “AntiYesOnSelf.exe”, which gives the contradictory answer of “YesO

23、nSelf.exe”. When an input causes “YesOnSelf.exe” to give an output “YES”, it gives “NO”.And, the problem comes. What will happen if we run “AntiYesOnSelf.exe” on itself?Luckily again, we only have two answers to discuss. If the output is “YES”, it means when it runs on itself, the output should be “

24、NO”, because “YesOnSelf.exe” should give “NO”. This makes no sense. On the other hand, if it gives “NO” as the output, the output should be “YES” according to “YesOnSelf.exe”.Anyway, the program can never exist logically. Let us see through the process. First we suppose that “AlwaysYes.exe” exists a

25、nd in that case, “YesOnSelf.exe” exists, which means “AntiYesOnSelf.exe” exists. Now, we can conclude “AlwaysYes.exe” never exists.EXAMPLE2 “CanCrash.exe”Sometimes we come across some unsatisfying circumstances that a program that we are running can crash during the process. Maybe we are always tryi

26、ng to find a way to detect whether a program can automatically crash. We can just call it “CanCrash.exe”, which gives “YES” when the input is an executable program and can crash by itself. Now we can use the same method to prove that this kind of program does not exist.Suppose we have REALLY made su

27、ch kind of program and compiled it into an executable program, and it can do exactly what we need it to do. Then we can easily make up such a program “CanCrashWeird.exe” as can crash based on the input whenever “CanCrash.exe” gives “YES”. Furthermore, we can create a program “CrashOnSelf.exe”, which

28、 do exactly as follows:When the input can crash, the new program crash, too.On other circumstances, it gives “NO”Similarly we can find that when we run the new program on itself, well get involved in a logical jam. Think of the outcomes. If it REALLY crashes, then it should crash due to the definiti

29、on. If it DOES NOT crash, then it should give “NO”, and that is what it does. It looks like that the answer is perfectly persistent on any circumstance. However, similarly to example 1, we can create the program “AntiCrashOnSelf.exe”, which do the opposite due to “CrashOnSelf.exe”. In that case, we

30、can similarly conclude this kind of program never exists, and, “CanCrash.exe” never exists.SIMILAR INTERESTING THINGS IN LOGICAL FIELDIn logics, there are some strange propositions that we can claim them neither true nor false. For example, here comes proposition “The proposition itself is false.” T

31、he proposition is neither true nor false. We can make assumptions to see clearly what it is. If it IS true, then it should be false according to itself. If it IS false, then the proposition is displaying the true fact, and it should be true. So it is neither true nor falseactually we cannot tell whe

32、ther it has the attribute of being true or false. This kind of proposition is called “paradox”, which is a mysterious part of logics.CONCLUSION & MOREWe can now come to the conclusion that some kind of program REALLY DOES NOT exist, even it is as easy as “AlwaysYes.exe” or as simple and useful a

33、s “CanCrash.exe”. We have to say we can exactly tell whether human beings logical system is complete.In that case, we have to think about more questions about our computers and ourselves.1. How can we deal with the possibility of programs crashing and shutting down if these problems are unpredictable