数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究构建一个用于将二进制自然数加1的图灵机？
图灵机 (TM) 可以用七元组形式描述为：
(Q,X, ∑, δ,q0,B,F)
其中：
Q 是一个有限的状态集。
X 是带字母表。
∑ 是输入字母表。
δ 是一个转移函数：δ:QxX->QxXx{左移, 右移}。
q0 是初始状态。
B 是空白符号。
F 是最终状态。
二进制数
1 = 1
2 = 10
3 = 11
4 = 100
5 = 101
6 = 110
. . .
算法
步骤 1 - 移动到字符串的右端。
步骤 2 - 重复
如果当前单元格包含 1，则写入 0 并向左移动，直到当前单元格包含 0 或空白。
步骤 3 - 写入 1。
步骤 4 - 移动到字符串的左端并停止。
让我们称之为 B。
TM 指令如下：
(0, 0, 0, R, 0) 向右扫描。
(0, 1, 1, R, 0) 向右扫描。
(0,B ,B , L, 1) 找到字符串的右端。
(1, 1, 0, L, 1) 写入 0 并向左移动，带有进位位。
(1, 0, 1, L, 2) 写入 1，加法完成。
(1,B , 1, S, Halt) 写入 1，完成并处于正确位置
(2, 0, 0, L, 2) 向左扫描。
(2, 1, 1, L, 2) 向左扫描。
(2, B, B , R, Halt) 达到字符串的左端并停止。
瞬时描述：11 + 1 =2？？？
状态 0 - B 1 1 B 向右扫描
状态 0 - B 1 1 B
状态 0 - B 1 1 B 扫描完成。
状态 1 - B 1 1 B 1 变为 0
状态 1 - B 1 0 B 1 变为 0
状态 1 - B 0 0 B 0 变为 1
停止 - B 1 0 0 B 完成！
更新于: 2021年6月16日
746 次浏览
广告