一個演算法可以用任意的高級編程語言表達嗎？

最近想入門演算法，想要在學習的同時用程序語言實踐，但是不知道用什麼編程語言比較好，所以有了如上問題

題主可能是想問一個簡單的問題，不幸問到了計算機理論的本原，哈哈。

目前發現的，最簡單的可以用來實現任意演算法的語言，運行效果如下圖：

借用百度的說明：

圖靈機，又稱圖靈計算、圖靈計算機，是由數學家艾倫·麥席森·圖靈（1912～1954）提出的一種抽象計算模型，即將人們使用紙筆進行數學運算的過程進行抽象，由一個虛擬的機器替代人們進行數學運算。

解釋一下圖靈機的要點：

一條無限長的紙帶。紙帶被劃分為一個接一個的小格子，每個格子上包含一個符號，符號是有限多個，比如a-z，另外有一個特殊的符號：空白。
紙帶上的格子從左到右依次被編號為0, 1, 2, ...。
一個可讀寫的機器頭。該機器頭可以在紙帶上左右移動，它能讀出當前所指的格子上的符號，並能改變當前格子上的符號。
機器頭自身可以保存一個狀態，狀態的取值比如S、N、W、E等有限多種狀態。
一套控制規則「狀態轉換表」。它根據當前機器所處的狀態以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作，並改變自身記錄的狀態。
例如：機器頭讀取到當前格子是b，當前狀態是S，則：

1. 寫入（替換）當前符號；
2. 移動機器頭，可以左移、右移，或者不移動；
3. 可以切換機器頭保存的狀態，比如S改為N，也可以不改。

然後神奇的事情是……數學家們證明了，這樣一種機器，可以模擬人類所能進行的任何計算過程。換句話說也就是可以表達任意演算法。

不要問我怎麼做到的，這種程序我也不會寫。【捂臉】

一開始的圖靈機有多種顏色、多種狀態，後來數學家們慢慢找到了越來越簡單的方法，目前極限是機器頭只需要兩個狀態，紙帶有三種顏色就夠了。（前面的圖中，機器頭可以是上、下，紙帶顏色有白、黃、橙）。

因為所有高級編程語言都可以模擬實現上述圖靈機，所以所有高級編程語言都可以用來表達演算法。

參考資料：

圖靈機_百度百科

維基百科 https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA

回到題主問題上：初學可以用Python，入門演算法或者試驗演算法都很快。

但是由於Python執行效率低，如果在網上刷演算法題，很多中、高難度問題會超時。所以專業一點還是要用C和C++。（C#的性能也還可以）。

語言不一定只能掌握一個，不管先學哪個都可以，總之先學起來再說。

直接回答問題，是，因為圖靈完備。

舉個例子來說，題主可以用java實現一個brainfuck解釋器，然後用這個解釋器實現一個C編譯器然後題主成功得到低級語言。

這個問題在理論上是trivial的，比如說題主可以自己證明一下partial recursive function都是Turing computable，甚至可以在一階語言的範疇里討論lambda calculus。後面這幾者和圖靈機的區別在於表示某些東西的時候，圖靈機可能比較啰嗦（嚴格定義的話，紙帶只表示0/1而且不是二進位，而是用1的個數來表示數字），在涉及證明的時候，idris N的定義就比圖靈機的定義要方便。

具體到某個工程問題了，如果涉及到內存（圖靈機），題主應該考慮自己需不需要用list來模擬內存來深入學習內存分配的問題（還可以手寫一個heap），這個和語言是不是「高級」才有關，我認為差異僅在於內存模型的不同，但本質上能表達的一定是一根無限長（阿列夫零）（有一端/無端都可以，是等價的）然後讀寫有限信息編碼（比如只有0/1還不是二進位表示）的紙帶，還有定位功能

但是要證明某個演算法超出了某類計算範圍（ackmann函數是原始遞歸函數不可表達的，這個函數是完全的但是沒辦法用正則極小化運算元表達，題主也可以自己證明證明），可能用一些高級語言更適合表達這個問題（crystal的hash可以是Int | Char=&>String的，題主可以考慮用C++如何表達這種東西，這就是是否方便的意思）當年我的老師就吐槽我那個證明寫得太長了……

所以建議是題主學高級語言也可以硬生生寫成低級的（手寫list heap），最好學點函數式編程可以介入別的理論，那麼高級、低級、邪教的編程語言你都掌握了，各種場景都可以應對了╮(╯▽╰)╭

HELLO，我猜想題主想問的不是圖靈完備，題主想問作為一名新人，學演算法用什麼語言。最近我一直在錄演算法相關的視頻和教程，也在整理相關訓練題集。這裡我先給個觀點:隨便。演算法大多是那種小而精美的程序。用一種語言寫，另一種是很好複製的。本質是要理解思路，難度不在語言本身。

演算法是語言無關的，演算法的本質是計算過程。『曹沖稱象』就是一種計算過程，也就是一種演算法，你可以用任何語言去表達。解魔方、解決數獨也是演算法。所以本質上演算法是語言無關的。

學習演算法最好的教材是《演算法導論》，學習入門演算法導論一本書足夠。演算法導論用的是偽代碼。這樣你就不用再糾結用什麼語言了。那些按照語言教演算法的書，往往抓不住重點。

但是肯定最後是需要一門語言來落地的，如果要我推薦的話，選你最熟悉的語言，或者你將來要用的語言（你感興趣什麼）。如果要我推薦，我覺得c++/java/py都很好。

《算導》更側重基本概念，是引導你學習演算法的一本書。比如排序，《算導》介紹的排序種類是相對比較少的，比如《演算法》介紹的就比《算導》多很多。但是，並不是越多越好，有時候入門越少越好。

讀《算導》要多久？收穫有多大？

個人的話，拿出半年時間，每天讀2個小時可以讀完一遍。收穫的話，寫程序速度能夠提高很多。設計系統的時候，會想到很多平時想不到的地方。

《算導》的證明怎麼看？數學知識需要學多深？

大家學習《算導》的一個痛點是前幾章的證明+數學對吧？我一開始也覺得困惑。這裡給大家簡單講講。

數學上，學習《算導》用的比較多的是比較淺的數學知識，並不複雜，主要有：

數列，多項式等
指數、對數
概率（學完條件概率）

我並不是說上面的數學知識是全部，但是是用的最多的。遇到其他，會也行，不會也行。演算法本質是計算過程，而不是數學。比如說lgn! = O(nlgn)，不能推導，那就記住好了。

關鍵難點在於：證明

我認為《算導》的精華就在這裡，比如利用「循環不變式」去證明「插入排序」的正確性。證明是《算導》的精華，數學上很簡單，等差數列求和。理解很困難，建議大家多度幾遍證明。

為什麼證明難學呢？因為《算導》的證明在糾正我們錯誤的思考方式。如果你所有證明都躲開了，那很有可能你錯過了最有價值，可以糾正你思維方式的部分。證明難懂本質上，個人認為是沒有預留足夠的學習時間，也沒有意識到這裡有礦，是認知問題。當然確實，有少數證明很難，比如說隨即打亂，快排平均時間的計算。遇到實在看不懂的，就跳過去就好了。（其實也並不難，而是需要概率知識）