圖靈機添加兩個數字

Question

如何創建圖靈機，它將計算兩個用＃號隔開的二進制數字的總和，例如。 111＃101B，其中B是空白的？結果可以寫在磁帶的末尾。

Answer 1

1. 寫一個圖靈機將兩個二進制數轉換爲一元（保持它們之間的空白）。
2. 寫一個圖靈機，用1代替空白，並從尾部切下一個數字。
3. 編寫一個圖靈機將一個一元數轉換爲二進制數。
4. 將這三臺機器鏈接在一起。

Answer 2

你沒有學過如何在小學增加數字。只是在這裏實施相同的事情。用天真的方法，這是二次時間。

進一步的加速是可能的。