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

14

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

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={n2n1}

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

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

Марцио де Биаси
источник
Я пытаюсь понять наиболее важные результаты работы , и я действительно удивлен арифметическая прогрессия теорема на странице 12. Пусть является крупнейшим нечетным делителем N . Тогда что будет D и M ? Возможно, я где-то что-то неправильно понял ...F(N)NDM
domotorp
Теперь я посмотрю на это, но вы уверены, что «самый большой нечетный делитель N» вычисляется с помощью 2CM?
Марцио Де Биаси
@domotorp: кстати, я задавал тот же вопрос и о mathoverflow , но не получил новых идей
Марцио Де Биаси
Я думаю, что если вы продолжите делить N на 2, пока не сможете, вы получите наибольший нечетный делитель, и это должно быть легко сделать.
domotorp
Хорошо, я думаю, что если (с нечетным x ) и 2 i - наибольшая степень двух, большая чем N , 2 l - наибольшая степень двух, большая, чем x , мы можем установить D = 2 i - 1 , М = 2 л - 1 . Неофициально, если N имеет i бит, тогда вы можете безопасно расширить самый старший бит N, добавив j 2 i - 1N=2kxx2iN2lxD=2i1M=2l1NiNj2i1и результат изменится на . j2l1
Марцио Де Биаси

Ответы:

10

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

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

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

Теорема 3.3 : Для любого фиксированное целое число , L K = { п K | п 0 } Т Уk2Lk={nkn0}TV


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

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

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

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

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

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