Является ли этот язык распознаваемым 3 символами ТМ в O (n log n)?

Я играл с очень интересным и все еще открытым вопросом « Азбука одноленточной машины Тьюринга » (Эмануэле Виола) и придумал следующий язык:

$L = \{ x \in \{0,1\}^n \text{ s.t. } |x| = n = 2^m \text{ and } count1(x) = k * m; \; n,m,k \geq 1 \}$

где - это число с в строке x. $count1(x)$ $1$

Например, если x = 01101111, то n = 8, m = 3, k = 2; так $x \in L$

Может ли L быть распознан машиной Тьюринга с одной лентой и алфавитом из 3 символов за шагов? $\{ \epsilon, 0, 1 \}$ $O(n \log{n})$

Если мы используем 4 символа, ответ - да:

проверьте, если заменяя с на и с на и в то же время сохраните с справа; $|x|=2^m$ $0$ $\epsilon$ $1$ $2$ $m$ $1$
затем посчитайте число с по модулю в . $2$ $m$ $O(n \log{n})$

Например:

....01101111....... input x  (|x| = 8 = 2^3)
000.021.1212.0001.. div 2, first sweep (000. can safely be used as a delimiter)
000.022.1222.00011. div 2, second sweep
000.022.2222.000111 div 2, third sweep --> m = 3 (= log(n) )
000..22.2222....111 cleanup (original 1s are preserved as 2)
000..22.2221102.... start modulo m=3 calculation
000..22.2210022.... mod 3 = 2
000..22.2000222.... mod 3 = 0
000..22.0012222.... mod 3 = 1
000..20112.2222.... mod 3 = 2
000..11122.2222.... ACCEPT

cc.complexity-theory turing-machines time-complexity Марцио де Биаси
источник

Если является натуральное число , представленное , чем всегда равна , и поэтому

| x | = n = 2^{m}

$\vert x \vert = n = 2^m$

x

$x$

c o u n t 1 (x)

$count1(x)$

1

$1$

L = {10}

$L = \lbrace 10 \rbrace$

Марк Бери

Извините | х | означает длину строки х. Пример: x = 01101111, n = 8, m = 3, k = 2 и, таким образом,

x \in L

$x \in L$

Марцио Де Биаси

Кстати, это отличный кандидат на вопрос Эмануэле, поскольку он находится в

: он не регулярен по лемме прокачки, поэтому не может быть , но это .

Θ (n \log n)

$\Theta(n \log n)$

o (n \log n)

$o(n \log n)$

O (n \log n)

$O(n \log n)$

Джошуа Грохов

Разве вы не можете использовать ту же идею, что и у случая с 4 символами , со следующими модификациями:

Всегда обрабатывайте пару символов одновременно.
$(00, 01, 10, 11) \mapsto (\epsilon0, \epsilon1, 0\epsilon, 1\epsilon)$ $\epsilon\epsilon$
Используйте аналогичный трюк для шагов "мод 2".

$O(1)$

Юкка Суомела
источник

Вы правы! ... теперь я подозреваю, что ответ на вопрос Эмануэле - да ... но он все еще открыт, так что, вероятно, это не так легко доказать формально :-( Спасибо!

Марцио Де Биаси

Является ли этот язык распознаваемым 3 символами ТМ в O (n log n)?

Ответы: