1樓：
計算機（包括圖靈機等類似計算模型）只是二階邏輯的物理實現，二階邏輯上不可判定的問題計算機當然也做不出來。
至於人工智慧之類的問題不是做不出來，只是不能在可行時間內計算出來。
2樓：楊個毛
Turing-Church Thesis：凡是能用物理裝置算出來的，計算機都能算出來。
注意這東西是個形式上不嚴密的猜想，有很多不同版本的描述，有的版本大家都相信為真，有的版本爭議更大。我個人是相信這個猜想的。
然而前面同學也說了，有些你能提出的問題是undecidable的，也就是說電腦是算不出來的。
如果你相信這個猜想的話，結合後面這一條，可以推出乙個很有意思的事情，就是這個世界上有很多問題，你能提出，但是你沒有任何通用方法解決。因為所有的方法（包括「用腦子想」）都是物理裝置。當然我覺得這個結論雖然看起來有點悲觀但是沒什麼違反直覺的地方，甚至仔細想想好像很有哲理的樣子。
回到前面乙個同學說計算機不能生成隨機數這件事情上，當然首先這是錯的，有可以生成隨機數的硬體……至於這些生成隨機數的硬體是不是「本質上是隨機的」，那可能要交給物理學家回答了。概率波的本質是什麼，上帝到底在不在擲骰子，我這種搞CS的人是不懂的，希望物理大神解答。
乙個更有意思的事情是，如果乙個生成隨機數的演算法雖然是偽隨機的，但是完全無法推出任何規律來（嚴格來說，是說「已知它之前生成的若干隨機數，你試圖以任何高於1/2+epsilon的準確度猜測它生成的下乙個bit」這個問題是undecidable的），你就沒有任何辦法把它和真隨機區分開。
也就是說，在承認強的Turing-Church Thesis的情況下，只要你能證明「區分A和B是undecidable的」，即使邏輯上A和B是兩個概念而且你並沒有證明它們就一定是一樣的，它們也再也不可能被區分開了。
好在應該不會有這樣的偽隨機演算法（我覺得應該可以證明，不過好累啊不想想了）
3樓：Trigger
這個問題可以從兩個角度來看。計算機不能解決的問題包括但不限於兩種（我沒想到別的case），一種是給定符合圖靈機模型輸入和輸出發現給不出來輸出的，這類問題如同高票答案所講，在計算理論裡被稱作undecidable problem。最經典的例子是停機問題，給定乙個函式，問這個函式會不會結束。
答案是不知道，計算機給不出這個答案。另一種是不好被抽象成乙個個decidable problem的問題，比如說人工智慧，讓計算機像人一樣思考，那這種例子太多，世界上一切計算機還沒做到的事情都可以算在其中。
如果問什麼是計算機確定做不到的，那麼計算理論裡，乙個問題（給定輸入輸出）是不是undecidable的這件事，很多是可以理論證明的，有一套reduction的套路。
至於題主說什麼不要說什麼p和np，我只想說，反智主義再見。
4樓：
計算理論中專門有一類問題叫不可解問題：Undecidable problem，另見 Sipser § 4.2。它們不可解是有證明的。
List of undecidable problems
這樣能不能解決電腦科學的百萬富翁問題？
知使用者 關鍵問題是這台機器不一定是可信的 然後我就寫了個這個 玩兒的就是心跳歸來 題主的方法顯然是錯的，百萬富翁問題裡是沒有可信的第三方的，題主給的機器就是第三方。關於這個問題matrix67中介紹過乙個方法，Matrix67 The Aha Moments 這個演算法也是姚期智先生關於百萬富翁問...
為什麼可以程式設計 程式能解決哪些問題 不能解決哪些問題
可以解決的是，可被描述為演算法的可計算問題。不可以解決的，就是他的對立面，不可描述為演算法，不可計算問題。舉個例子 1 1 等於幾，這是可以計算的，加數 被加數可以數位化，加法的演算法明確，一步可以出結果。同理，複雜計算可以無線分割成小的計算的疊加。這些是可計算問題。不可計算問題，比如 生命的意義是...
打架不能解決問題，為啥打仗能解決問題呢？
聖約大先生 蟹妖。文無第一，武無第二。如果網路發展成規定對噴的雙方必須要面對面解決問題，那至少中國的網際網路將是一片淨土。秀才遇到兵. 漫捲詩書 戰爭是政治鬥爭的延續，有時可以做到以打促和，有時可以成為談判或妥協的資本。而打架，壓根就沒有打仗所具備的各種條件，打架有種種理由 可以為乙個女人，也可以為...