НГУ
http://forum.nsu.ru/

Машины Тьюринга и Шёнфилда
http://forum.nsu.ru/viewtopic.php?f=18&t=23046
Страница 1 из 4

Автор:  Pavel E. Alaev [ Пт фев 17, 2012 10:28 pm ]
Заголовок сообщения:  Машины Тьюринга и Шёнфилда

У меня есть несколько вопросов по этим машинам. Просьба специалистам по возможности высказаться.

Первый вопрос: есть известная теорема Агравала-Каяла-Саксены, которая говорит, что множество простых чисел полиномиально вычислимо. Спрашивается, что это означает? Если мы излагаем теорию алгоритмов на основе машин Тьюринга, это означает следующее. На ленту машины выкладывается число , записанное в максимально короткой форме. Такая запись занимает символов. Затем запускается алгоритм, который за шагов, где - длина входа, определяет, является ли простым.

В итоге мы получаем алгоритм, который за шагов определяет простоту числа .

Вопрос 1: если мы излагаем теорию алгоритмов на основе машин Шёнфилда, как мы можем сформулировать эту теорему? Ведь у нас нет ленты, значит, нет понятия "длина входа". Регистры машины Шёнфилда безразмерны и могут содержать в себе любое число.

Автор:  Коба [ Сб фев 18, 2012 3:42 pm ]
Заголовок сообщения:  Re: Машины Тьюринга и Шёнфилда

Pavel E. Alaev писал(а):
На ленту машины выкладывается число , записанное в максимально короткой форме.


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

Pavel E. Alaev писал(а):
В итоге мы получаем алгоритм, который за шагов определяет простоту числа .

Если мне не изменяет память, .

Pavel E. Alaev писал(а):
Вопрос 1: если мы излагаем теорию алгоритмов на основе машин Шёнфилда, как мы можем сформулировать эту теорему?

А никак не можем!!!

Машина Тьюринга - достаточно адекватная модель реальных вычислительных устройств в плане сложности вычислений. Машина Шёнфилда, увы, всего лишь вычисляет за конечное время то, что вычислимо за конечное время на МТ. Для изложения теории сложности она не годится.

Автор:  Pavel E. Alaev [ Пн фев 20, 2012 1:21 pm ]
Заголовок сообщения:  Re: Машины Тьюринга и Шёнфилда

Коба писал(а):
А никак не можем!!!

По-видимому, действительно так. Мы могли бы ввести длину входа аксиоматически: например, если при запуске МШ в некоторых ячейках находятся ненулевые числа , то длиной входа можно было бы считать . Но в этом случае, например, задача распознавания равенства двух чисел x и y станет экспоненциально сложной: если в двух регистрах МШ лежат x и y, то легко показать, что меньше чем за \min(x,y) шагов вопрос об их равенстве точно не решить.

На одноленточной МТ эта задача решается за квадратичное время, а на двухленточной - за линейное.

Тогда у меня вопрос к В.П.: Вы, кажется, по работе располагаетесь поближе к сложности вычислений: понятию "число шагов работы алгоритма" у вас какое точное определение даётся?

Автор:  salmin [ Пн фев 20, 2012 6:56 pm ]
Заголовок сообщения: 

эх, а даже я не знал, что есть такая теорема. чему учился столько лет :)

Автор:  В.П. [ Пн фев 20, 2012 8:32 pm ]
Заголовок сообщения:  Re: Машины Тьюринга и Шёнфилда

Pavel E. Alaev писал(а):
Тогда у меня вопрос к В.П.: Вы, кажется, по работе располагаетесь поближе к сложности вычислений: понятию "число шагов работы алгоритма" у вас какое точное определение даётся?

Бывают разные модели вычислений. Как правило в модели формально определяется сложность вычислений, а понятие по смыслу подобное "числу шагов работы алгоритма" есть не всегда. Приведу два примера, когда подобное понятие есть.
1. Ветвящиеся программы (BDD http://en.wikipedia.org/wiki/Binary_decision_diagram ). Это такой ориентированный граф без циклов со степенью исхода 2, каждая внутренняя вершина дерева помечена некоторой переменной. Граф имеет начальную вершину и две конечные 0 и 1. Если переменная равна 0 идём в левого сына, 1 - в правого. Если значение булевой функции 0, то должны попасть в конечную вершину 0. Здесь "числу шагов работы алгоритма" соответствует глубина схемы - число вершин в самом длинном ориентированном пути. Аналогично определятся глубина в разных схемах из функциональных элементах, контактно-вентильных схемах и т.д.
2.Клеточные автоматы http://en.wikipedia.org/wiki/Cellular_automaton
Это такой ориентированный граф, в каждой вершине которого помещена функция, переменными которой служат значения в соседних вершинах. За один такт одновременно пересчитываются значения во всех вершинах. "Число шагов работы алгоритма" - это, конечно, число тактов. Аналогично определяется число шагов алгоритма для разных специализированных конечных автоматов ( игра "жизнь", дискретная генная сеть).

Автор:  Pavel E. Alaev [ Пн фев 20, 2012 9:17 pm ]
Заголовок сообщения:  Re: Машины Тьюринга и Шёнфилда

В.П. писал(а):
Бывают разные модели вычислений. ...

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

Верно ли, что любые два сотрудника ИМ, вообще как-то связанные с конечными графами и алгоритмами, понимают её смысл одинаково? Или у нас есть разные модели вычислений, и один сотрудник может считать, что фраза верна, а другой - что неверна?

P.S. Что-то старая гвардия на форум подтянулась! То IVM выплыл из глубины веков, то вот salmin...

Автор:  В.П. [ Пн фев 20, 2012 10:15 pm ]
Заголовок сообщения:  Re: Машины Тьюринга и Шёнфилда

Pavel E. Alaev писал(а):
В.П. писал(а):
Бывают разные модели вычислений. ...

Я, может быть, имел в виду не столько Вашу узкую специальность, сколько дискретную математику в целом.

Сложность вычислений точно не моя узкая специальность.
Pavel E. Alaev писал(а):
Верно ли, что любые два сотрудника ИМ, вообще как-то связанные с конечными графами и алгоритмами, понимают её смысл одинаково? Или у нас есть разные модели вычислений, и один сотрудник может считать, что фраза верна, а другой - что неверна?

Если определено в каком виде задан граф (длина входа), то "сложность вычисления" в крупном масштабе (линейная, полиномиальная, NP и т.д.) понимается однозначно. Так как все "разумные" вычислительные преобразования в данном масштабе имеют вполне определённую сложность.

Автор:  Коба [ Вт фев 21, 2012 11:33 am ]
Заголовок сообщения:  Re: Машины Тьюринга и Шёнфилда

Pavel E. Alaev писал(а):
...задача распознавания равенства двух чисел x и y станет экспоненциально сложной: если в двух регистрах МШ лежат x и y, то легко показать, что меньше чем за \min(x,y) шагов вопрос об их равенстве точно не решить.

На одноленточной МТ эта задача решается за квадратичное время, а на двухленточной - за линейное.

С другой стороны прибавление единицы на МШ происходит мгновенно, а на МТ на это требуется хотя бы и линейное, но всё же время...

Автор:  Pavel E. Alaev [ Вт фев 21, 2012 2:11 pm ]
Заголовок сообщения:  Re: Машины Тьюринга и Шёнфилда

В.П. писал(а):
Если определено в каком виде задан граф (длина входа), то "сложность вычисления" в крупном масштабе (линейная, полиномиальная, NP и т.д.) понимается однозначно.

С графом в смысле входа картина довольно ясная: если число вершин равно N, он задаётся матрицей NxN из 0 и 1, и длину входа можно по умолчанию считать равной N^2 с точностью до константы.

Но чтобы достичь такого тотального единомыслия, нужны ведь какие-то определения? У меня вопрос, в чём они состоят. Как на практике определяется число шагов алгоритма, хотя бы примерно?

Автор:  В.П. [ Вт фев 21, 2012 4:33 pm ]
Заголовок сообщения:  Re: Машины Тьюринга и Шёнфилда

Pavel E. Alaev писал(а):
Но чтобы достичь такого тотального единомыслия, нужны ведь какие-то определения? У меня вопрос, в чём они состоят. Как на практике определяется число шагов алгоритма, хотя бы примерно?

Обычно алгоритм состоит из известных операций: арифметические, полный перебор, сортировка, какие-то задачи класса NP (поиск клики, гамильтонова цикла и т.д.). Для каждой операции верхняя оценка числа операций известна, остаётся правильно оценить параметры операций.

Автор:  Pavel E. Alaev [ Вт фев 21, 2012 8:33 pm ]
Заголовок сообщения:  Re: Машины Тьюринга и Шёнфилда

В.П. писал(а):
Обычно алгоритм состоит из известных операций: арифметические, полный перебор, сортировка ... Для каждой операции верхняя оценка числа операций известна ...

На практике этого, наверное, достаточно. Но странно, что нет общепринятого стандартного определения. Не Моисей же сообщил человечеству эти оценки.

Автор:  В.П. [ Вт фев 21, 2012 8:46 pm ]
Заголовок сообщения:  Re: Машины Тьюринга и Шёнфилда

Pavel E. Alaev писал(а):
В.П. писал(а):
Обычно алгоритм состоит из известных операций: арифметические, полный перебор, сортировка ... Для каждой операции верхняя оценка числа операций известна ...

На практике этого, наверное, достаточно. Но странно, что нет общепринятого стандартного определения. Не Моисей же сообщил человечеству эти оценки.

Нет ну я полагал, что в конечном счёте оценки сводятся к вычислениям на Машине Тьюринга. Формальное определение класса NP обращается именно к ней.

Автор:  Коба [ Ср фев 22, 2012 8:57 am ]
Заголовок сообщения:  Re: Машины Тьюринга и Шёнфилда

В.П. писал(а):
Нет ну я полагал, что в конечном счёте оценки сводятся к вычислениям на Машине Тьюринга. Формальное определение класса NP обращается именно к ней.

Ага, я тоже всегда так полагал. И вроде в книге Пападимитроу написано то же самое. Моисей = Алан Тьюринг :)

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

P. S. Кстати, есть такая теорема: язык является регулярным (распознаётся конечным автоматом) тогда и только тогда, когда он распознаётся на недетерминированной МТ за линейное время. Вот про это я слышал лишь краем уха, хотелось бы где-нибудь прочитать подробнее.

Автор:  guest [ Ср фев 22, 2012 1:39 pm ]
Заголовок сообщения:  Re: Машины Тьюринга и Шёнфилда

Коба писал(а):
А никак не можем!!!


Как то даже обидно за машины...

Pavel E. Alaev писал(а):
По-видимому, действительно так. Мы могли бы ввести длину входа аксиоматически: например, если при запуске МШ в некоторых ячейках находятся ненулевые числа , то длиной входа можно было бы считать .


Эти логарифмы называются логарифмическим весовым критерием для определения сложности вычисления операций на машинах Шенфилда, с произвольным доступом к памяти (RAM), и т.п. Противовес - равномерный весовой критерий, где от размера числа сложность выполнения операции не зависит.

Вот типичные утверждения из "метрической" теории алгоритмов, которой Коба отказалв существовании :):


Цитата:
Для любой k-ленточной машины Тьюринга M существует такая моделирующая ее машина с произ.дост. к памяти R, что при равномерном весовом критерии и при логарифмическом весовом критерии.


Цитата:
При логарифмическом весовом критерии для любой РАМ R существует моделирующая ее пятиленточная машина Тьюринга M такая, что . При равномерном полиномиально невозможно.

Автор:  guest [ Ср фев 22, 2012 1:50 pm ]
Заголовок сообщения:  Re: Машины Тьюринга и Шёнфилда

В.П. писал(а):
Нет ну я полагал, что в конечном счёте оценки сводятся к вычислениям на Машине Тьюринга. Формальное определение класса NP обращается именно к ней.


Ничто не мешает сформулировать эту проблему в терминах недетерминированных машин с произвольным доступом к памяти, где вопрос полиномиальности никуда не исчезает.

Страница 1 из 4 Часовой пояс: UTC + 7 часов
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/