Другие проблемы

• Проблема разрешения (Entscheidungsproblem‎)

• Выводимость формулы в арифметике Пеано

• Проблема соответствий Поста (англ.)

• Вычисление колмогоровской сложности произвольной строки

• Идеальный архиватор, создающий для любого входного файла программу наименьшего возможного размера, печатающую этот файл ^[3]

• Идеальный оптимизирующий по размеру компилятор ^[4]

• Десятая проблема Гильберта

• Определить, можно ли замостить плоскость данным набором плиток Ванга (англ.)

• Определить, можно ли замостить плоскость данным набором полимино

• Проблема унификации (англ.) второго и высшего порядков

• Проблема вывода типов в модели Хиндли — Милнера с rank-N полиморфизмом

Проблемы, алгоритмическая неразрешимость которых не доказана

Для некоторых задач неизвестен алгоритм, решающий их, и по своей природе они похожи на известные алгоритмически неразрешимые задачи. Вопросы об алгоритмической разрешимости таких задач являются открытыми проблемами. Вот некоторые из таких задач:

• Аналог десятой проблемы Гильберта для уравнений степени 3

• Аналог десятой проблемы Гильберта для уравнений в рациональных числах

• Проблема умирающей матрицы для матриц порядка 2

48) Машина Поста

Машина Поста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (Emil L. Post), которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».

Принцип работы

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты (см. пример ниже). Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (т. е. состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:

i K j,

где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд:

V j - поставить метку, перейти к j-й строке программы.

X j - стереть метку, перейти к j-й строке программы.

<- j - сдвинуться влево, перейти к j-й строке программы.

-> j - сдвинуться вправо, перейти к j-й строке программы.

? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.

! – конец программы (стоп).

У команды «стоп» отсылки нет. После запуска возможны варианты:

• работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);

• работа может закончиться командой Stop;

• работа никогда не закончится.

• Пример: вычитание натуральных чисел P — Q

Будем представлять натуральное (целое неотрицательное) число P набором из P+1 единиц и разделять числа нулём. Исходное положение каретки помечено символом «v»

v

00111110111000

P Q

Сложение двух чисел тривиально — достаточно поставить 1 между ними и стереть крайний правый символ у Q. Программа вычитания состоит из последовательного затирания крайних левых меток у Q и правых у P:

1. 0 - стираем левый символ у Q

2. →

3. ? 5, 4

4. Stop - стоп если затерли Q=0

5. ←

6. ? 7, 5 - цикл поиска P

7. 0 - стираем правый символ у P

8. →

9. ? 1, 8 - ищем Q

Отметим, что номер команды перехода не указывается, если переход происходит на следующую по порядку строку (для наглядности текста). В 6-ой строке возможно зацикливание, если Q > P (вы можете добавить проверку сами)

49

Машины с неограниченными регистрами (МНР)

Вы­бран­ный на­ми ги­по­те­ти­че­с­кий ком­пь­ю­тер на­зы­ва­ет­ся ма­ши­ной с не­огра­ни­чен­ны­ми ре­ги­стра­ми (МНР) [Кат­ленд,1983,16-29]; он яв­ля­ет­ся лег­ким ви­до­из­ме­не­ни­ем ма­шин, впер­вые рас­смо­трен­ных Дж.Шепердсоном и Х.Стерджисом (1963) и по­лу­чив­ших на­зва­ние РАМ (рав­но­до­ступ­ная ад­рес­ная ма­ши­на) и РАСП (рав­но­до­ступ­ная ад­рес­ная ма­ши­на с хра­ни­мой про­грам­мой). Эти мо­де­ли в бо­ль­шей сте­пе­ни, чем ма­ши­на Тью­рин­га от­ра­жа­ют струк­ту­ру сов­ре­мен­ных вы­чис­ли­те­ль­ных устройств.

МНР со­дер­жит бес­ко­неч­ное чис­ло ре­ги­стров, обоз­на­ча­емых че­рез R₁,R₂,R₃,..., каж­дый из ко­то­рых в лю­бой мо­мент вре­ме­ни со­дер­жит не­ко­то­рое на­ту­ра­ль­ное чис­ло, при­чём чис­ло, со­дер­жа­ще­еся в R_n, бу­дем обоз­на­чать че­рез r_n. Это мож­но изоб­ра­зить сле­ду­ющим об­ра­зом:

МНР мо­жет из­ме­нять со­дер­жи­мое ре­ги­стров с по­мо­щью не­ко­то­рой ко­ман­ды. Каж­дая ко­ман­да мо­жет быть од­но­го из сле­ду­ющих че­ты­рех ви­дов: ко­ман­да об­ну­ле­ния, ко­ман­да при­бав­ле­ния еди­ни­цы, ко­ман­да пе­ре­ад­ре­са­ции и ко­ман­да усло­вно­го пе­ре­хо­да (см.таблицу 1).

 

Таблица 1. Команды МНР и их операционная семантика

Ариф­ме­ти­че­с­ки­ми ко­ман­да­ми на­зо­вём ко­ман­ды об­ну­ле­ния, при­бав­ле­ния еди­ни­цы и пе­ре­ад­ре­са­ции, при­чём ко­ман­ды Z(n) и S(n) со­от­ве­т­ст­ву­ют про­стей­шим опе­ра­ци­ям над на­ту­ра­ль­ны­ми чис­ла­ми в фор­ма­ль­ной ариф­ме­ти­ке.

Про­грам­ма МНР - это ко­неч­ная по­сле­до­ва­те­ль­ность ко­манд. На­ча­ль­ной кон­фи­гу­ра­ци­ей на­зы­ва­ет­ся по­сле­до­ва­те­ль­ность a₁,a₂,...

на­ту­ра­ль­ных чи­сел, со­дер­жа­щи­х­ся в ре­ги­страх R₁,R₂,....

Что­бы МНР при­сту­пи­ла к вы­чис­ле­ни­ям (ра­бо­те), она до­лжна быть снаб­же­на про­грам­мой P и на­ча­ль­ной кон­фи­гу­ра­ци­ей.

Пусть P«(I₁,I₂,...I_s), где I₁,I₂,...I_s - по­сле­до­ва­те­ль­ность ко­манд. Вна­ча­ле МНР вы­пол­ня­ет ко­ман­ду I₁.

Опре­де­лим ин­ду­к­тив­но по­ня­тие "сле­ду­ющая ко­ман­да в вы­чис­ле­нии".

Определение.

(1) I₁ - сле­ду­ющая ко­ман­да в вы­чис­ле­нии.

(2) Ес­ли I_k (k=1,2,...,s-1) не яв­ля­ет­ся ко­ман­дой усло­вно­го

пе­ре­хо­да, то ко­ман­да I_k+1 яв­ля­ет­ся сле­ду­ющей ко­ман­дой в вы­чис­ле­нии.

(3) Ес­ли I_k (k=1,2,...,s-1) яв­ля­ет­ся ко­ман­дой J(m,n,q), а r_m и r_n - те­ку­щее со­дер­жи­мое ре­ги­стров R_m и R_n со­от­ве­т­ст­вен­но, то сле­ду­ющей ко­ман­дой в вы­чис­ле­нии яв­ля­ет­ся ко­ман­да I_q, q=1,2,...,s, ес­ли r_m=r_n, и ко­ман­да I_k+1 - в про­тив­ном слу­чае.

(4) Ес­ли I_s яв­ля­ет­ся ко­ман­дой J(m,n,q), а r_m и r_n - те­ку­щее со­дер­жи­мое ре­ги­стров R_m и R_n со­от­ве­т­ст­вен­но, то сле­ду­ющей ко­ман­дой в вы­чис­ле­нии яв­ля­ет­ся ко­ман­да I_q, ес­ли r_m=r_n и q£s.

(5) Ни­ка­ких дру­гих сле­ду­ющих ко­манд в вы­чис­ле­нии нет.

Определение.

Бу­дем го­во­рить, что сле­ду­ющая ко­ман­да от­сут­ст­ву­ет, ес­ли:

(1) I_s яв­ля­ет­ся ариф­ме­ти­че­с­кой ко­ман­дой;

(2) I_s яв­ля­ет­ся ко­ман­дой J(m,n,q), при­чём r_m=r_n и q>s;

(3) I_s яв­ля­ет­ся ко­ман­дой J(m,n,q), при­чём r_m¹r_n. В этом слу­чае го­во­рят, что вы­чис­ле­ние оста­но­ви­лось по­сле вы­пол­не­ния ко­ман­ды I_s, а за­клю­чи­те­ль­ной кон­фи­гу­ра­ци­ей бу­дем на­зы­вать по­сле­до­ва­те­ль­ность r₁,r₂,r₃,... со­дер­жи­мых ре­ги­стров на этом ша­ге.

Определение.

Бу­дем го­во­рить, что вы­чис­ле­ние оста­нав­ли­ва­ет­ся, ес­ли сле­ду­ющая ко­ман­да от­сут­ст­ву­ет.

МНР ра­бо­та­ет, по­ка вы­чис­ле­ние не оста­но­ви­т­ся.

Предложение.

Для каж­дой ко­ман­ды пе­ре­ад­ре­са­ции T(m,n) су­ще­ст­ву­ет про­грам­ма, не со­дер­жа­щая ко­манд пе­ре­ад­ре­са­ции, ко­то­рая на вся­кой кон­фи­гу­ра­ции МНР да­ет тот же ре­зу­ль­тат, что и T(m,n).

До­ка­за­те­ль­ст­во. Упраж­няй­тесь!

Та­ким об­ра­зом, ко­ман­да пе­ре­ад­ре­са­ции в опре­де­ле­нии МНР яв­ля­ет­ся из­бы­то­чной; тем не ме­нее, пред­став­ля­ет­ся ес­те­ст­вен­ным и удоб­ным иметь та­кие ко­ман­ды, т.к. они об­лег­ча­ют по­стро­ение про­грамм.

Замечание.

Срав­ни­те МНР с ма­ши­ной с ре­ги­стра­ми об­ще­го на­зна­че­ния (см.[Уокерли,1984,с.184-192]

Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен