НГУ

Я не спорю, что какую-то теорию сложности для машин Шёнфилда можно развить. В конце-концов, есть же понятие абстрактной меры сложности, связанные с нею теоремы об ускорении, о пробелах и т. п.

Вот только какова практическая ценность всего этого? На практике нас прежде всего интересует временная сложность. И вот тут с машинами Шёнфилда начинаются чудеса. В частности, сложение двух чисел требует экспоненциального времени и т. п. (напомню, что в машине Шёнфилда, несмотря на наличие "произвольного доступа к памяти", есть только две команды: инкремент и декремент). А это, несмотря на логическую непротиворечивость соответствующей теории, явная глупость: на двухленточной МТ сложение производится за линейное время!!! Что соответстветствует реальной практике вычислений на современных компьютерах. И опять же на современных компьютерах инкремент выполняется за линейное время (если мы работаем с очень большими числами и как-то реализуем длинную арифметику). А МШ выполняет этот инкремент мгновенно.

Короче, можно развивать теорию сложности вычислений для МШ, никто этому не мешает, но эта теория, увы, не будет отражать реальную практику вычислений. А вот для МТ всё Ок, это достаточно адекватная модель любого вычислительного устройства. Хоть с прямым доступом к памяти, хоть без такового.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

А что, кто-то утверждал, что мешает?

У меня такое впечатление, что guest слабо представляет себе устройство машины Шёнфилда. Несмотря на наличие прямого доступа к памяти, это машина с крайне ограниченным набором допустимых команд. Последнее является решающим фактором

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

Да, Вы оказались правы. В этой связи два вопроса как к специалисту. Первый, имеется ли другие, может быть более распространенные, названия для этих машин, например, счетчиковые. Второй, чем примечательна эта вычислительная модель среди других вычислительных моделей, что она изучается, несмотря на ее отрыв от реальности. Частная модель в фундаментальном курсе, на мой частный вкус и цвет, это странно.

Возможно.

У нас в НГУ данное идеальное устройство принято называть "машина Шёнфилда". Насколько я понимаю, это связано с тем, что когда впервые поменяли программу на факультете и перенесли курс теории алгоритмов на первый семестр, первым этот курс прочитал проф. А. С. Морозов. И он дал этим машинам такое название. С его лёгкой руки название прижилось.

Но, думаю, А. С. Морозов здесь не "пионер". Он строил свой курс на основе курса Пападимитроу, который тот читал в MIT (Массачусетсткий технологический). Я уже давно не перечитывал тот оригинал, но, возможно, термин "машина Шёнфилда" идёт оттуда.


Эта модель очень удобна для изложения "чистой теории вычислимости". Она допускает очень простую кодировку.

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

Однако, помня о том, что теория сложности всё же важна, лично я в своём курсе ввожу и те, и другие машины. "Основная теорема" у меня доказывается так: функция частичнорекурсивна - > она вычислима на машине Шёнфилда - > она вычислима на машине Тьюринга - > она частичнорекурсивна. Первые две стрелки в этом круге из трёх доказываются довольно просто, и машина Шёнфилда выступает при такой схеме доказательства просто в качестве промежуточного инструмента. Если же сразу доказывать вычислимость на МТ произвольной частичнорекурсивной функции традиционным методом (китайская теорема об остатках из теории чисел, элиминация примитивной рекурсии и т. д.), получается сложнее с технической точки зрения.

Мой коллега С. Л. Березнюк, читающий курс ТА на параллельном потоке, одними лишь машинами Шёнфилда и обходится. У него теорема такая: функция частичнорекурсивна -> она вычислима на МШ -> она частичнорекурсивна. Всё получается ещё проще, поскольку у МШ и кодировки более простые. Однако теория сложности остаётся при таком подходе как бы "за бортом". В конце курса, когда всё же приходится заводить разговор о сложности вычислений, он рисует МТ и, "размахивая руками", пытается убедить студентов в том, что это тоже универсальное вычислительное устройство, наряду с МШ. Я же не считаю, что на математическом факультете доказательство теорем методом "размахивания руками" - удачная мысль. Всё же математику преподаём, а не философию, и если делаем какое-то утверждение, то желательно его строго доказывать

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

Большо спасибо за ответ. То есть МШ используются по методологическим причинам.

И все же, кажется, что утверждение, что их использовать для изучения теории сложности, не совсем верно. Точнее, не имея точного ответа, я углядываю некоторые аналогии в этом вопросе с λ-исчислением. Казалось бы, для ЛИ вопрос о сложности бесмысленен. Тем не менее, какую-то теорию по этому вопросу пытаются развивать [Arnold Beckmann. Exact bounds for lengths of reductions in typed λ-calculus // Journal of Symbolic Logic. 66(3):1277-1285, 2001].

Наверное это не очень интересно чистым математикам, но этой задачей сильно озабочены люди, занимающиеся анализом функциональных программ. В качестве забавного примера. Городок регулярно посещает иностранный товарищ, который (может быть и не первый) используя λ-исчисление доказал, то оптимальное основание для системы счисления - это основание натурального логарифма. То, что это довольно просто доказывается в других областях не отменяет замечательности этого факта - где λ-исчисление и где натуральные логарифмы...

Так что, вероятно, развить теорию сложности можно и для МШ. Поэтому вопрос в другом. Вопрос - нужно ли? Человечество давно уже научилось строить вычислители, намного более сложные чем счетчиковые машины и соответствующие им формальные модели также универсальны в теории.

Ну а с методолгической точки зрения - все верно и понятно.

Лучше один раз увидеть:
http://aturingmachine.com/index.php
http://www.youtube.com/watch?v=cYw2ewoO6c4

_________________
Наука умеет много гитик.

У меня сложилось впечатление, что когда речь идёт о точном подсчёте степени, стандартом является использование многоленточных МТ. Но не буду настаивать. Вот, кстати, ссылка на некоторый вариант статьи про полиномиальность простых чисел, со странички одного из авторов:
http://www.cse.iitk.ac.in/users/manindr ... ity_v6.pdf

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

Итоговая оценка числа шагов в статье выглядит как , т.е. , где m - длина входного числа.


Честно говоря, тоже не понимаю, зачем она там изучается.


Гм, в первый раз услышал, что для доказательства вычислимости ч.р.ф. на МТ нужна элиминация примитивной рекурсии. Для МТ можно строить макросы точно так же, как для МШ. Если же некоторое число макросов уже построено, то разница между вычислением минимизации и прим. рекурсии на МТ почти незаметна: обе реализуются минут за 10.

Ну... на МШ макросы проще.

А вообще-то надо подумать. Возможно, выкинуть в следующем году МШ из курса будет удачной идеей... По крайней мере, попробовать можно.

P. S. На текущий момент затраты времени у меня таковы. Одна лекция тратится на всё, что касается МШ (рассказ о том, как устроена машина, с примерами программ + теорема об элиминации макросов + теорема о том, что любая чрф вычислима на МШ). На теорему о том, что любая функция, вычислимая на МШ, вычислима на МТ, тратится примерно полторы лекции (половина лекции на формальное определение МТ плюс лекция на саму теорему). Итого: две с половиной лекции на доказательство того, что любая чрф вычислима на МТ. При этом всё приходится расписывать крайне подробно, помня о том, что лекции читаются для первокурсников.

Если, вводя макросы для МТ (одноленточной), удастся изложить теорему о том, что любая чрф вычислима на МТ, быстрее, чем за 2.5 лекции (по прежнему помня о недостатке навыков у первокурсников и расписывая все доказательства очень подробно), то это будет просто замечательно!!!

P. P. S. Нам в своё время рассказывали вычислимость на МТ произвольной чрф именно через элиминацию примитивной рекурсии. Очень быстро и сжато. Но это было в четвёртом семестре, то есть в конце второго курса. К тому времени уже сформировавшегося математического мышления оказалось достаточно, чтобы самостоятельно заполнять все пробелы в доказательствах.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

С прямым доступом к памяти, об этом тоже не стоит забывать

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

Некоторое число "макросов" указано в сборнике задач Лаврова-Максимовой. Их использование называется там "композицией МТ".


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


Гм, если мы говорим про МТ, там прямого доступа к памяти нет. Извольте побегать по лентам туда-сюда.

Если для примера взять статью про простые числа, то они в части алгоритмов ссылаются на "Modern Computer Algebra". Я её немного почитал, авторы там вообще отказываются от точной формализации машин, с которыми работают. Тем самым оценки из этой книги и статьи, типа O~(m), являются отчасти условными. Похоже, что в книге используется прямой доступ к памяти, но непонятно, насколько существенно. Я пока не смог понять, можно ли перемножить два m-битных числа на многоленточной МТ за O~(m) шагов, там очень сложный алгоритм.

Ещё один основной источник, Handbook of Theoretical Computer Science, вместо одного канонического варианта машин вообще даёт целое море разных подходов, довольно далёких друг от друга. Возможно, пестрота картины объясняется тем, что авторы подходов пытаются строить машины, максимально близкие к современным компьютерам, а поскольку достичь этого каждый раз не удаётся, в итоге получаем гору испорченного металла.

Но при всём многообразии машин они обладают общим свойством: если какая-то задача попала в класс P на одной, то попала в P и на другой. МШ в этом смысле являются откровенными уродцами.

На самом деле есть. По крайней мере в книге Пападимитроу такая модификация описана. Имеем 2 ленты, на одной читаем "адрес" (то есть номер ячейки второй ленты), после его прочтения мгновенно туда перескакиваем.

С остальным согласен. Макросы, думаю, как-нибудь сам изобрету

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

Мне всегда казалось, что под брендом "МТ" у нас идут устройства, в которых нет никакой мистики, кроме неограниченных фондов на закупку лент. Если мы начинаем чудесным образом летать вдоль ленты, не задаваясь вопросом, как это у нас получается, получаем в чистом виде RAM.

Спор о терминах обычно имеет мало смысла, так что заранее соглашаюсь. Хотя мне казалось, что отличительной чертой "бренда" МТ является наличие лент и считывающего устройства, обозревающего не более одной ячейки ленты на каждом конкретном шаге работы. А ползать или летать - это уже детали.

Ну да ладно, я уже сказал, что спорить не буду.

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind

Да, это действительно спор о терминах. В конце концов, есть же понятие МТ с оракулом, которая совсем не то же самое, что просто МТ.

Хотя если говорить просто про МТ, без всяких добавок, то её популярность, возможно, основана на том, что она может быть реализована как реальное устройство, и в силу этого является самой "медленной" из всех возможных машин. Один шаг работы МТ - это действительно один шаг работы алгоритма, а не неведомая куча шагов, замаскированная под один.

В этом смысле МТ с прямым доступом к памяти сильно не похожа на обычные МТ, при всём их многообразии. Мы за 100 шагов можем написать в адресной ячейке 10^12 в двоичном виде и перескочить сразу на триллион клеточек вправо. Но МТ с оракулом похожа на МТ ещё меньше.

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

На них можно реализовывать массивы с линейным доступом к памяти: если отводить по одной строке на ячейку памяти, то передвижение головки к строке n, где n записано в первой ячейке, будет занимать n шагов. Это либо вообще не испортит сложность алгоритма по сравнению с RAM, либо увеличить степень на 1, что можно потерпеть. Например, при сортировке методом "пузырька" всё равно приходится двигаться вдоль массива, поэтому линейный доступ к памяти вообще ни на что не повлияет. Насколько я помню программирование, там иногда применяется организация массивов в виде списков, как раз с линейным доступом.

И вообще, двумерные МТ забавны.