波斯特-圖靈程式

波斯特-圖靈程式(Post-Turing program)一種用於字元串操作的抽象機的程式.

波斯特-圖靈程式(Post-Turing program)一種用於字元串操作的抽象機的程式.假設這種抽象機有一條雙向無窮帶作為存儲裝置，帶上劃分為若干小格，每個格子上可以寫一個符號，這種抽象機還有一個帶頭，每一時刻它都指向一個小格，並可以左右移動.抽象機僅有四條指令，它們的功能如下:

PRINT a:在帶頭指向的格子上寫符號a.

IF a GoTo 1:如果帶頭指向的格子上為符號。則轉到標號為1的指令去執行;否則，執行下一條指令.

RIUHT:帶頭向右移一小格.

LEFT:帶頭向左移一小格.

開始時，帶上可以放若干個符號作為輸人，並可以指定帶頭指向的符號.用以上四種指令(加上標號)，可以編出各種波斯特一圖靈程式.執行程式後，帶上的非空白符號就是程式的輸出.