歡迎關(guān)注我的專欄( つ??ω??)つ【人工智能通識(shí)】
所有數(shù)學(xué)問(wèn)題都可以用計(jì)算機(jī)來(lái)解決嗎强法？
如上一篇繁忙的海貍Busy beaver中所展示的，海貍是否會(huì)陷入無(wú)法停機(jī)的無(wú)限循環(huán)湾笛？這個(gè)看似簡(jiǎn)單的數(shù)學(xué)問(wèn)題就無(wú)法完全用計(jì)算機(jī)來(lái)徹底解決饮怯，或者說(shuō)它是不可計(jì)算的。
可計(jì)算性Computability/Calculability
可計(jì)算性是指某個(gè)數(shù)學(xué)問(wèn)題是否可以用計(jì)算機(jī)在有限步驟內(nèi)徹底解決迄本。
首先必須是數(shù)學(xué)問(wèn)題硕淑，而不能是給我做個(gè)漢堡包這種需要真實(shí)的實(shí)體變化的問(wèn)題。
其次必須是有限步驟嘉赎，如果這個(gè)問(wèn)題的算法遠(yuǎn)遠(yuǎn)超過(guò)計(jì)算機(jī)目前可能擁有的計(jì)算能力置媳，那么也應(yīng)該視為不可計(jì)算的。
研究問(wèn)題的可計(jì)算性質(zhì)可以避免浪費(fèi)時(shí)間在無(wú)底的坑里面做無(wú)意掙扎公条。
關(guān)于問(wèn)題
可計(jì)算性是針對(duì)問(wèn)題而言的拇囊，問(wèn)題又主要是以下兩類：
- 判定問(wèn)題Decision Problem。判定問(wèn)題就是回答是或否的問(wèn)題靶橱。一個(gè)典型的決策問(wèn)題是：大數(shù)據(jù)集U及其子集S寥袭，元素u屬于大數(shù)據(jù)集U，判斷u是否屬于子集S关霸。比如自然數(shù)中的n是否屬于質(zhì)數(shù)传黄，這就是一個(gè)判定問(wèn)題，當(dāng)然我們可以采用試除算法來(lái)判定
不可判定就是已經(jīng)確定無(wú)法對(duì)這種問(wèn)題進(jìn)行正確回答队寇，要么答不對(duì)膘掰，要么陷入死循環(huán)永遠(yuǎn)答不出。比如繁忙海貍中的停機(jī)問(wèn)題就是一個(gè)不可判定問(wèn)題佳遣。
- 功能問(wèn)題Function Problem识埋。功能問(wèn)題比判定問(wèn)題更復(fù)雜，不能只回答是或否零渐，可能需要回答一個(gè)數(shù)字窒舟，比如關(guān)于一個(gè)自然數(shù)的因數(shù)個(gè)數(shù)，或者地圖導(dǎo)航到某地最近路線是哪條诵盼，這種問(wèn)題的答案就需要一個(gè)數(shù)字或一條路徑才行惠豺。
另外還有搜索問(wèn)題Search Problem(在對(duì)象Y中是否能夠找到符合要求的結(jié)構(gòu)x)和最優(yōu)化問(wèn)題Optimization Problem(多個(gè)解決方案中哪一個(gè)更優(yōu)）。
計(jì)算模型Model of computation
圖靈機(jī)是一種抽象的計(jì)算模型拦耐，理論上可以實(shí)現(xiàn)無(wú)限多種算法耕腾，類似的計(jì)算模型（功能模型Functional models）還有以下幾個(gè)，他們都被認(rèn)為是圖靈等價(jià)或圖靈完整Turing completeness的：
- λ演算Lambda calculus杀糯，λ-calculus。阿隆佐·邱奇Alonzo Church在20世紀(jì)20~30年代發(fā)明苍苞。
- 組合邏輯Combinatory logic固翰。摩西·施菲克爾Moses Sch?nfinkel和哈斯克爾庫(kù)里Haskell Curry在20世紀(jì)20~30年代發(fā)明狼纬。
- μ-遞歸函數(shù)μ-recursive functions。μ音miu骂际。最早在1934年由哥德?tīng)柼岢觥?967年疗琉，馬文閔斯基指出μ-遞歸函數(shù)與圖靈機(jī)等價(jià)。
- 寄存器機(jī)Register machine歉铝。由馬文閔斯基和其他幾位科學(xué)家?guī)缀跬瑫r(shí)在1961年發(fā)明盈简。
可計(jì)算理論
如上所示，遞歸理論起源于20世紀(jì)30年代太示，由庫(kù)爾特·哥德?tīng)朘urtG?del柠贤，阿隆佐·邱奇Alonzo Church，羅莎·培特RózsaPéter类缤，阿蘭·圖靈Alan Turing臼勉，斯蒂芬·克萊尼Stephen Kleene和埃米爾·珀斯特Emil Post等人提出。
早在1936年就邱奇和圖靈就受到哥德?tīng)柕牟煌陚湫远ɡ淼膯l(fā)餐弱，算法程序不可能正確的判斷任意數(shù)學(xué)問(wèn)題的真假宴霸。后來(lái)這個(gè)理論就被稱為Church-Turing論文，定義了可計(jì)算概念的含義：可由算法計(jì)算的函數(shù)都是可計(jì)算函數(shù)膏蚓。
可計(jì)算性的提出瓢谢，也意味著科學(xué)家們對(duì)不可計(jì)算問(wèn)題的認(rèn)可，證明了數(shù)學(xué)中確實(shí)存在無(wú)法有效解決的問(wèn)題驮瞧。
此外還有描述可計(jì)算程度的相對(duì)可計(jì)算性Relative computability 和圖靈度Turing degrees氓扛。
歡迎關(guān)注我的專欄( つ??ω??)つ【人工智能通識(shí)】
每個(gè)人的智能新時(shí)代
如果您發(fā)現(xiàn)文章錯(cuò)誤，請(qǐng)不吝留言指正剧董；
如果您覺(jué)得有用幢尚，請(qǐng)點(diǎn)喜歡；
如果您覺(jué)得很有用翅楼，歡迎轉(zhuǎn)載~
END
