2007-10-28から1日間の記事一覧

On the proof of the universarity of the 2,3-Turing machine

2-color cyclic tag systemが計算万能性を有していることが知られているので,2,3-Turing machineでそれをエミュレートすることで万能性を示している. System 0が2,3-Turing machineで, 以下System 5まである. 5まで変形してそれで2-color cyclic tag syste…