批次圖靈完成嗎？

我找不到它，是否非常好奇 - 如果它沒有資格，它缺少什麼功能來限定？我已經完成了相當數量的批量工作，並沒有發現任何明顯的能力偏差。批次圖靈完成嗎？

來源

2012-06-20 PinkElephantsOnParade

我相信它有資格。圖靈完備性的基本要求被認爲可以簡化爲幾個簡單的操作，包括：存儲狀態（變量）的能力，分支能力（條件）以及迭代能力（循環）。批處理具有所有這些特性，所以除非對圖靈完備性有一些尚未發現的要求，否則批處理腳本是合格的。

來源

2012-06-20 19:20:59 Wug

我還會指出人們設法做一些完全荒謬的事情，只使用純批量腳本。：S – Wug

我覺得這比它略微多一些。圖靈機不僅僅是「存儲狀態」，它基本上是一個雙端堆棧。 FSM具有弱狀態，分支和迭代版本，不是TC。 PDA甚至有一個堆棧，但仍然不是TC;它需要一個有兩個堆棧的PDA作爲TC。 –

我只是（因爲brainfuck被證明是圖靈完整的）「證明」批是圖靈完備，通過創建一個批處理解釋brainfuck：

https://github.com/YoYoYonnY/Brainfuck-In-Batch

順便說一句，一個圖靈完備編程語言意味着其可以：

不可能創造一個能確定是否存在另一個程序（在相同的語言），最終會停止或將繼續運行下去（我不知道這個是如何工作的，我不要以爲任何人Ver使用這個來證明圖靈的完整性）。
可以創建可在語言上運行的所有可能的程序的程序（A解釋：Brainfuck interpreter in Brainfuck（有一個更好的版本，這點我很遺憾不能找到這個人是非常慢））
可能採取行動像或模擬圖靈機，並因此包含至少以下幾個方面：
- 寫入存儲器（即改變的可變值爲任何其他值;只能夠改變true到false和周圍的其他方法是仍然有效。在批次的情況下：SET A=5）
- '無限'記憶（即我可以寫多個位/字節，最好是無限多。只要我們可以寫入整個對象，字符串，數組，表格，位域甚至只是整數都是有效的。請注意，必須可以通過地址讀取和寫入變量：如果要使整數有效，必須有位移，並且必須能夠索引數組，例如array[index];。）
- 條件跳轉語句（即IF %A%==0 GOTO LABEL（跳轉到標籤如果A是零），while (var) {/*code*/}（跳轉回到開始的代碼，而VAR不爲零）或jmp0 exit;（跳轉到退出如果堆棧上的當前值爲零））

傳統的圖靈機需要你有一個雙方無限的磁帶，但是一個簡單的數組，字符串，表（對象）或二進制數（位域）將會也工作。例如，在我的「Brainfuck in Batch」中，我使用了一個類似數組/表格的對象來存儲內存（因爲batch允許您更改數值的鍵，如下所示：SET ARRAY[%KEY%]=%VALUE%）

來源

2015-05-10 12:58:04 YoYoYonnY

批次圖靈完成嗎？

回答

相關問題