使用图灵机指定给定序列的成员

Question

我遇到的一个问题是，给定一个二进制序列 a_0, ..., a_{n-1} 它需要多少次转换才能在给定一个非负整数 i 时输出a_i 如果 i < n，否则为 0。您可以假设输入以 1 开头，除非 i 为 0。

使用 https://martinugarte.com/turingmachine/ 我模拟了以下图灵机来尝试了解它应该采用多少个状态

具有 n=2、5 个转换的序列

//Sequence is 0,1
name: Sequence
init: one
accept: end

one,0
end,0,-

one,1
two,_,>

two,_
end,1,-

two,0
end,0,-

two,1
end,0,-

已测序，n=3，8 个转换

//Sequence is 0,1,0
name: Sequence
init: one
accept: end

one,0
end,0,-

one,1
two,_,>

two,_
end,1,-

two,0
three,_,>

two,1
end,0,-

three,_
end,0,-

three,0
end,0,-

three,1
end,0,-

n=4、11 个转换的序列

//Sequence is 0,1,0,1
name: Sequence
init: one
accept: end

one,0
end,0,-

one,1
two,_,>

two,_
end,1,-

two,0
three0,_,>

two,1
three1,_,>

three0,_
end,0,-

three0,0
end,0,-

three0,1
end,0,-

three1,_
end,1,-

three1,0
end,0,-

three1,1
end,0,-

据此我猜测指定一个 n 长的序列大约需要 O(n) 个状态。你能证明这一点吗？

Answer 1

这是归纳出来的。假设基本情况为 n=2，下面的图灵机可以很容易地修改为适用于任意长度的 2 序列

//Sequence is 0,1
name: Sequence 
init: one
accept: end

one,0 end,0,-

one,1 two,_,>

two,_ end,1,-

two,0 end,0,-

two,1 end,0,-

现在对于归纳步骤，假设它适用于长度 n 并且按上面的顺序排列。如果我们像 six0101 那样为 10101x 指定它们，我们将替换最小的那个结束，按过渡在该点作用的数字排序，例如，

six0101,0
end,0,-

作用于 101010。使此转换转到三个新的转换，在示例中它将转到 seven01010，空白时将输出 a_n 并停止。在 0,1 上它会输出 0 并停止。这向图灵机添加了 3 个转换。满足归纳步骤。

事实上，这证明了对于二进制图灵机，所需状态的上限为 3n-1 个转换。这可以推广到具有以下上限的 c 字符图灵机 (c+1)n-1

使用图灵机指定给定序列的成员

Specifying members of a given sequence with a Turing Machine

algorithm

math

turing-machines