|
圖靈機是1936年Alan Turing提出的一個計算機模型。這種計算機由一個一維數(shù)組（或者叫磁帶）構(gòu)成，還有一個可以左右移動的指針。磁帶上每個格子里都有一種顏色（共可從m種顏色中選擇），指針本身則可以是n種狀態(tài)中的一種。給定一個m*n的表格，你就定義了一個圖靈機。這個表格告訴機器，如果當前指針的狀態(tài)是x，它所指的格子的顏色是y，那么下一步機器應該把這個格子染成什么顏色，然后指針應該左移一位還是右移一位，指針的新狀態(tài)又是什么。有了一個圖靈機后，我們便可以把它當做一個計算機進行數(shù)據(jù)處理了。我們可以給這個圖靈機編寫一個初始狀態(tài)（也就相當于現(xiàn)在所說的程序和數(shù)據(jù)），讓它按照這個表格不斷執(zhí)行下去，對數(shù)據(jù)進行處理并“輸出”適當?shù)慕Y(jié)果來。 能夠模擬其它所有圖靈機的圖靈機叫做“通用圖靈機”(UTM, Universal Turing Machine)。不是所有的圖靈機都是通用的：很多圖靈機只能完成一些特定的運算，而只有通用圖靈機才能完成更一般的操作，是一臺“通用的”機器。這些通用圖靈機就像現(xiàn)代計算機一樣，可以用來編程執(zhí)行各種各樣的操作，能實現(xiàn)現(xiàn)代計算機的各種功能。我們經(jīng)常說一種程序語言是圖靈完全的(Turing Complete)，指的就是這種語言等價于通用圖靈機，能夠執(zhí)行任何一種復雜的數(shù)學運算。 50年代起，科學家們瘋狂地尋找通用圖靈機，所需要的顏色數(shù)和狀態(tài)數(shù)越來越小。最好的結(jié)果是1967年由Marvin Minsky得到的，他發(fā)現(xiàn)了一個7,4通用圖靈機，即一個只需要7種狀態(tài)，4種顏色的通用圖靈機。人們開始好奇，最簡單的通用圖靈機是什么樣子的。2002年，Stephen Wolfram（沒錯，就是MathWorld的那個Wolfram）做出了一個重大的突破：他發(fā)現(xiàn)了一個2,5通用圖靈機，并且給出了一個很可能是通用圖靈機的2,3圖靈機。很早以前人們就證明了，不存在2,2的通用圖靈機；因此如果Wolfram提出的2,3圖靈機是通用圖靈機的話，它就是最小的通用圖靈機了。但Wolfram始終不能證明這個2,3圖靈機是通用的，于是在今年三月份用25000美元懸賞征解。 昨天，英國伯明翰大學的一名20歲在校大學生Alex Smith提交了一篇55頁的論文，證明了Wolfram的2,3圖靈機與另一個已知的通用機器等價，從而證明了2,3圖靈機是最簡單的通用圖靈機，證實了這個很早就已經(jīng)提出的猜想，解決了長期以來計算機科學界的一大疑問。這是一個意義非常重大的突破，無疑是信息學界中的一件激動人心的大事。 做人要厚道 轉(zhuǎn)貼請注明出處 新聞來源：來源1 來源2 |
|
|
來自： AMI66 > 《mathematica》
