我最近遇到了以下問題：圖靈機設計
給圖靈機圖的圖靈機上輸入一個字符串
x ∈ {0, 1}∗暫停（接受）與將頭包含磁帶的左端字符串x′ ∈ {0, 1}∗位於左端（否則爲空），其中x'是字典順序中x的後繼字符串;即序列ε, 0, 1, 00, 01, 10, 11, 000, . . .中的下一個字符串，其中字符串按照增加的長度順序列出，其中的字符串由相應的整數值分開。 （簡要記錄您的TM）
我很困惑如何開始爲它設計合適的解決方案。我能否首先設計這臺機器，然後再選擇圖靈機？
圖靈機
首先，你需要了解圖靈機是什麼，並通過圖靈機，我假設你是在談論一個Universal Turing Machine。這是由計算機科學教父Alan Turing創建的概念機器。
機器由一些組件組成。首先，一個包含輸入的無限磁帶。喜歡的東西..
1-0-1-1-1-1-0-1-0-1-0
然後是一組規則..
if 1 then 0
if 0 then 1
所以當機器打1，輸出爲0，按照該規則。我們將機器定義爲在讀取頭設置爲時的值。讀頭像圖靈機中的當前位置。所以它會去..
1-0-1-1
^------------Current head.
然後下一個迭代：
1-0-1-1
^----------Current Head
這臺機器實際上是模擬逐位NOT功能。您也可以在圖靈機中設置一個狀態，例如：
if 1 then enter state 1
if 0 then enter state 0
大不了？例如突然，現在你可以做類似的東西：
1. if 1 and in state 1 output 1 and enter state 0
2. if 1 and in state 0 output 0 and enter state 1
3. if 0 and in state 0 output 1 and enter state 1
4. if 0 and in state 1 output 0 and enter state 0
而且我們定義一個狀態作爲我們的默認狀態。在這個例子中，我們稱之爲state 0。所以當機器啓動時，它看到一個1.那麼我在state 0，我剛剛得到了一個1，所以我打算做規則編號2。輸出0並輸入state 1。下一個號碼是0。那麼我在state 1，所以我打電話給規則號4。看看這是怎麼回事？通過添加狀態，你真的打開了你能做的事情。
現在，通用圖靈機是所謂的Turing Complete。這意味着它可以計算任何可計算的序列。包括你的任務的規範！
你的任務
因此，讓我們看看你的作業在圖靈機的情況下。
本機的目的是打印出來..
0 1 00 01 11 000 001 011 111
因此，我們知道，我們需要保持狀態。我們也知道國家需要越來越深入。因此，如果您的用戶類型爲000，我們需要知道我們有三個字符可以輸出。
而在家庭作業幫助方面，這恐怕我應該負責任地給你。對圖靈機的很好的理解，加上對你需要做什麼的理解，應該會使你的研究成爲解決方案的開始。