Может ли машина с двумя счетчиками решить

Можно стандартно два счетчика ( ) машина со следующими инструкциями: $c_1,c_2$

1) ADD 1 to c_i, GOTO label_j
2) IF c_i = 0 GOTO label_j, OTHERWISE SUB 1 to c_i and GOTO label_k
3) GOTO label_j
4) HALT and ACCEPT|REJECT

выбрать следующий язык:

L = {n^{2} ∣ n \geq 1}

$L = \{ n^2 \mid n \geq 1 \}$

(вход изначально загружен в счетчик ) ?. $c_1$

Это все еще открытая проблема? (ср. Рич Шропель, «Машина с двумя счетчиками не может рассчитать » [1972]) $2^N$

fl.formal-languages counter-automata Марцио де Биаси
источник

Я пытаюсь понять наиболее важные результаты работы , и я действительно удивлен арифметическая прогрессия теорема на странице 12. Пусть

является крупнейшим нечетным делителем

. Тогда что будет

? Возможно, я где-то что-то неправильно понял ...

F (N)

$F(N)$

N

$N$

D

$D$

M

$M$

domotorp

Теперь я посмотрю на это, но вы уверены, что «самый большой нечетный делитель N» вычисляется с помощью 2CM?

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

@domotorp: кстати, я задавал тот же вопрос и о mathoverflow , но не получил новых идей

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

Я думаю, что если вы продолжите делить N на 2, пока не сможете, вы получите наибольший нечетный делитель, и это должно быть легко сделать.

domotorp

Хорошо, я думаю, что если

(с нечетным

) и

- наибольшая степень двух, большая чем

- наибольшая степень двух, большая, чем

, мы можем установить

. Неофициально, если

имеет

бит, тогда вы можете безопасно расширить самый старший бит

добавив

N = 2^{k} x

$N = 2^k x$

x

$x$

2^{i}

$2^{i}$

N

$N$

2^{l}

$2^{l}$

x

$x$

D = 2^{i - 1}

$D=2^{i-1}$

M = 2^{l - 1}

$M = 2^{l-1}$

N

$N$

i

$i$

N

$N$

j 2^{i - 1}

$j 2^{i-1}$ и результат изменится на

j 2^{l - 1}

$j 2^{l-1}$

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

Ответы:

Проблема была решена в:

Оскар Х. Ибарра, Николас Ч. Трэн, Записка о простых программах с двумя переменными, Теоретическая информатика, том 112, выпуск 2, 10 мая 1993 года, страницы 391-397, ISSN 0304-3975, http: //dx.doi .org / 10.1016 / 0304-3975 (93) 90028-R .

Пусть - класс языков, распознаваемых машинами с двумя счетчиками. $TV$

Теорема 3.3 : Для любого фиксированное целое число , $k \geq 2$ $L_k = \{ n^k \mid n \geq 0 \} \notin TV$

Примечание: странно, что в газете «Ибарра и Тран»

Теорема 3.4. Пусть - полная функция с бесконечным диапазоном и такая, что соотношение для всех не выполняется ни для одной тройки ; тогда не может быть вычислено ни одной машиной с двумя счетчиками. $f$ $f(a + bn)=f(a)+cn$ $n \geq 0$ $(a,b,c)$ $f$

доказано, и авторы говорят, что оно было получено в несколько иной форме в:

И. М. Барздин, Об одном классе машин Туринга (машины Минского), русский, Алгебра и Логика 1 (1963) 42-51

но не цитируйте статью Рича Шрёппеля (1972), в которой также получена теорема ... :-)

Марцио де Биаси
источник

Я не уверен, что когда-либо странно, что двадцатилетняя газета не цитируется: по-видимому, авторы об этом не знали, как и судьи.

Дэвид Ричерби

@DavidRicherby: Мне было бы любопытно посмотреть, чем теорема в Schroeppel (1972) отличается от соответствующей теоремы в Barzdin (1963) :-) ... но у меня нет доступа к статье Барздина

Marzio De Biasi