用圖靈機指定給定序列的成員

Question

我遇到的一個問題是，給定二進制序列a_0，...，a_ {n-1}需要多少次過渡，以便在給出非負數整數我輸出a_i如果我< n和否則爲0。你可以假設輸入與1開始，除非我是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,- 

從這我猜想它大致是O（n）狀態指定一個序列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 + 1）的c字符的圖靈機器n-1