【計算機算不了的函數是什麼樣的?】現在人工智慧很熱,但計算機也有很多事情做不了,就連有的函數計算機都算不了。不是人類能力有限設計不出程序來算它們,而是在理論上這些函數就是無法計算的。

馬耀基博主就構造兩個無法計算的函數,一個是反對角線函數,一個是程序結束函數。思路大概這樣:

給所有一元程序編碼,這些程序對應了所有能計算的一元函數。因為按前面的定義,能計算的函數就是能用程序計算的,而所有的一元程序都在這裏了,所以可計算的一元函數也全在這裏。構造一個函數,這個函數與任意一個可計算的一元函數,都最少一個在某一個輸入值時輸出不同。這個函數叫反對角線函數。反對角線函數和所有可計算的函數不同,所以是不可計算的。

另一個是程序結束函數,它能判斷任一個程序在任一個輸入下是否結束。程序結束函數是無法計算的。有兩種證明方法。1、如果程序結束函數能夠用程序計算,那反對角線函數就能計算。2、如果程序結束函數能夠用程序計算,那就能設計出一個程序,當這個程序把自己的號碼作為輸入時,會出現矛盾。

你覺得他的這個設想如何?http://t.cn/R8beIPo

LINE it!
分享至google+
╰( ◕ ᗜ ◕ )╯ 快點加入POP微博粉絲團!
回頁頂