空間限定2次元交代チューリング機械の閉包性

概要

論文の詳細を見る
本報告では、空間限定2次元交代チューリング機械と3方向2次元交代チューリング機械によって受理される集合族の閉包性に関して考察する。2-ATM (L(m, n)) (TR2-ATM(L(m, n)))をL(m, n)空間限定2次元チューリング機械(空間限定3方向2次元交代チューリング機械)によって受理される集合族とする。ここで、L(m, n) : N^2 → N⋃{0} (Nは正の整数のすべての集合)は、2個の変数m(=入力テープの行数)とn(=入力テープの列数)をもつ関数とする。本報告では、(i)任意の関数g(n) = o(logn) (g(n) = o(logn/log log n))と1次元決定性チューリング機械によって構成可能な任意の非減少単調関数f(m)に対して、2-ATM(L(m, n))とTR2-ATM(L(m, n))は列連接、列+および射影に関して閉じていないことと、(ii)任意の関数f (m) = o(log m) (f(m) = o(log m/log log m))と1次元決定性チューリング機械によって構成可能な任意の非減少単調関数g(n)に対して、2-ATM(L(m, n))とTR2-ATM(L(m, n))は行連接、行+および射影に関して閉じていないことを示す。ここで、L(m, n) = f(m) + g(n) (L(m, n) = f(m) × g(n))とする。
社団法人電子情報通信学会の論文
1999-12-10