圖靈機比較二進制

Question

我想寫，用圖靈模擬，所以在形式：
0 1 * r 0 0 0 * r 0 0 # * * 3 0 x * r 0 0 y * r 0

...一個程序，它由「>」例如分隔的兩個二進制值1010> 111，這將停止 - 是，如果左側>右側，並停止 - 否左側>右側。

我想比較解決方案，如果您有興趣，請留下您的解決方案。

Answer 1

一些僞代碼的方法我可以使用：

1. 地帶出從LHS和RHS所有前導零用一些符號替換它們 - （不爲空，但不爲0，1，或>）。

2. 檢查以確保LHS和RHS中的剩餘位數相同。如果不是，我們可以根據相對長度立即說出LHS> RHS。通過來回跳動並將0,1更改爲0'，1'來做到這一點，直到/除非您在一側沒有標記出需要的標記。

3. 如果我們仍在檢查，現在的過程很簡單：比較LHS和RHS的第一個數字;如果LHS（1）> RHS（1），那麼LHS> RHS;如果LHS（1）< RHS（1），LHS < RHS。如果LHS（1）= RHS（1），則刪除這兩個，然後再重複第3步。如果所有的數字都沒有了，那麼這些數字是相等的，你停下來 - 不。

步驟＃1在輸入長度爲O（n），因爲我們可以從左到右進行一次掃描。然後我們可以回滾到磁帶的開頭。由於TM基本上執行n個步驟，n-1個步驟，...，2個步驟= n（n + 1）/ 2 - 1個步驟，所以步驟＃2是O（n^2） LHS和RHS。

步驟＃3是O（n^2），因爲TM基本上做n/2步n/2次，總共大約n^2/4步。

因此時間複雜度爲O（n^2），空間複雜度爲O（n）（我們將輸入用作臨時存儲器）。