В.Э.: Уже со студенческих времен я не могу понять, почему все «теоретики от алгоритмов» так
держатся за эти «машины Тьюринга». Ну, предложил 23-летний юноша (только что окончивший
университет и ставший «research fellow-ом» или, по-нашему, «научным сотрудником») Алан Тьюринг
такую модель в мае 1936 года, когда в мире не существовало еще ни одного компьютера. Ну, было по тем
временам это, пожалуй, действительно выдающимся достижением. Но с тех пор прошло 74 года – целая
человеческая жизнь! Компьютеры теперь есть в каждом доме, с ними знаком почти каждый ребенок,
основы компьютерного программирования учат в школе на уроках информатики! Если, как утверждает
Пенроуз, машины Тьюринга эквивалентны компьютерам, то почему бы всѐ, что он хочет нам сказать об
алгоритмах и процедурах, не продемонстрировать на примере настоящих (пусть идеализированных – в
смысле бесконечной памяти и т.д.) компьютеров? Почему Пенроузу надо лезть в это беспросветное болото
«тьюринговых машин», в которое ни один уважающий себя компьютерный программист за ним не
последует? ПОЧЕМУ? Пенроуз не знает компьютеров? Или на реальных компьютерах все эти рассуж-
дения не получаются? «Теоремы» не выходят? Они получаются только в Тьюринговых болотах?
Здравствуйте, Vaako, Вы писали:
V>«Теоремы» не выходят? Они получаются только в Тьюринговых болотах?
Именно. В Тьюринговых болотах теоремы доказываются элементарно, потому что правила работы МТ очень просты. Так что достаточно доказанных для МТ теорем плюс единственной теоремы о том, что реальная архитектура сводится к МТ, и все, больше ничего делать не надо.
Здравствуйте, Vaako, Вы писали:
V> В.Э.: Уже со студенческих времен я не могу понять, почему все «теоретики от алгоритмов» так V>держатся за эти «машины Тьюринга». Ну, предложил 23-летний юноша (только что окончивший V>университет и ставший «research fellow-ом» или, по-нашему, «научным сотрудником») Алан Тьюринг V>такую модель в мае 1936 года, когда в мире не существовало еще ни одного компьютера. Ну, было по тем V>временам это, пожалуй, действительно выдающимся достижением. Но с тех пор прошло 74 года – целая V>человеческая жизнь! Компьютеры теперь есть в каждом доме, с ними знаком почти каждый ребенок, V>основы компьютерного программирования учат в школе на уроках информатики! Если, как утверждает V>Пенроуз, машины Тьюринга эквивалентны компьютерам, то почему бы всѐ, что он хочет нам сказать об V>алгоритмах и процедурах, не продемонстрировать на примере настоящих (пусть идеализированных – в V>смысле бесконечной памяти и т.д.) компьютеров? Почему Пенроузу надо лезть в это беспросветное болото V>«тьюринговых машин», в которое ни один уважающий себя компьютерный программист за ним не V>последует? ПОЧЕМУ? Пенроуз не знает компьютеров? Или на реальных компьютерах все эти рассуж- V>дения не получаются? «Теоремы» не выходят? Они получаются только в Тьюринговых болотах?
Ну так, раз ты умнее какого-то там 23-летнего научного сотрудника, выпускника Кембриджа, члена Лондонского королевского общества, то изобрети свою принципиально новую модель компьютера. Мы все дружно будем на тебя молиться.
Здравствуйте, Vaako, Вы писали:
V> В.Э.: Уже со студенческих времен я не могу понять, почему все «теоретики от алгоритмов» так V>держатся за эти «машины Тьюринга». Ну, предложил 23-летний юноша (только что окончивший V>университет и ставший «research fellow-ом» или, по-нашему, «научным сотрудником») Алан Тьюринг V>такую модель в мае 1936 года, когда в мире не существовало еще ни одного компьютера. Ну, было по тем V>временам это, пожалуй, действительно выдающимся достижением. Но с тех пор прошло 74 года – целая V>человеческая жизнь! Компьютеры теперь есть в каждом доме, с ними знаком почти каждый ребенок, V>основы компьютерного программирования учат в школе на уроках информатики! Если, как утверждает V>Пенроуз, машины Тьюринга эквивалентны компьютерам, то почему бы всѐ, что он хочет нам сказать об V>алгоритмах и процедурах, не продемонстрировать на примере настоящих (пусть идеализированных – в V>смысле бесконечной памяти и т.д.) компьютеров? Почему Пенроузу надо лезть в это беспросветное болото V>«тьюринговых машин», в которое ни один уважающий себя компьютерный программист за ним не V>последует? ПОЧЕМУ? Пенроуз не знает компьютеров? Или на реальных компьютерах все эти рассуж- V>дения не получаются? «Теоремы» не выходят? Они получаются только в Тьюринговых болотах?
Вообще говоря, Тьюринг не ставил перед собой цель изобрести то, что сегодня называется компьютером. Он решал совершенно иную задачу,
поставленную еще Д.Гильбертом: entscheidungsproblem (проблема разрешимости). Тьюринг заинтересовался этой проблемой. По ходу поиска решения он предложил модель вычислителя, которую сегодня называют "машиной Тьюринга".
Уже потом, в 50-е годы эта машина стала настоящей "звездой" и сыграла большую (ну очень большую) роль при построении теории рекурсивных функций (начало
которой было положено работами Сколема, Геделя, Клини, Черча и того же Тьюринга). Но это уже другая история
Если интересно, гляньте для начала сюда: http://samag.ru/archive/article/1092
Там в конце хороший список литературы.
А болото можно сделать из чего угодно — хоть из машины Тьюринга, хоть из любого современного ЯП: было бы желание
Приходиться заниматься гадостью — зарабатывать на жизнь честным трудом (Б.Шоу)
Вообще, если интересоваться именно алгоритмами, а не вопросами завершимости-в-целом, то МТ и не используется особо, берутся другие модели, где есть хотя бы RAM, они уже намного ближе к реальным компам.
Здравствуйте, Дениc, Вы писали:
Д>Ну так, раз ты умнее какого-то там 23-летнего научного сотрудника, выпускника Кембриджа, члена Лондонского королевского общества, то изобрети свою принципиально новую модель компьютера. Мы все дружно будем на тебя молиться.
Я не буду. Согласно тому же Тьюрингу (и Черчу с Дойчем), все они разновидности одного и того же.
P.S. Тьюринг заслуживает уважения своей работой, а не тем, откуда он выпускался. Кстати, в Кембридже, насколько я знаю, не одно учебное заведение. В одно из таких кембриджских заведений Т. сдать экзамен не смог, учился в другом. Какая разница, он свое место в истории застолбил, личностью, а не местом.
Здравствуйте, D. Mon, Вы писали:
DM>Здравствуйте, Дениc, Вы писали:
Д>>то изобрети свою принципиально новую модель компьютера.
DM>Не, автор предлагает взять существующий x86 и теоремы на нем доказывать.
Я даже представить себе такое не могу. Как он собирается формализовывать модель современного процессора архитектуры x86 (а может, лучше x86_64 или ARM?) и не получить в сухом остатке модель машины Тьюринга?
математическая теория алгоритмов занимается вопросом разрешимости алгоритмов, а не их прикладному применению
машина Тьюринга очень проста и при этом эквивалентна "математической" вычислительной мощности реальных компов. точнее даже не, она превосходит ее, так как обладает бесконечной памятью.
Д>Я даже представить себе такое не могу. Как он собирается формализовывать модель современного процессора архитектуры x86 (а может, лучше x86_64 или ARM?) и не получить в сухом остатке модель машины Тьюринга?
после формализации модели современного процессора машины Тьюринга в остатке никак не получится
Получится конечный автомат.
Здравствуйте, dilmah, Вы писали: __>>машина Тьюринга очень проста D>Она корявая. Нормальные алгоритмы маркова, лямбда-исчисление и т.п. изящнее МТ.
в нашем универе теорию алгоритмов у меня один одногруппник, который сейчас уже сильно продвинулся на научной карьере, называл теорией онанизма
я оттуда ничего не помню, кроме слов "рекурсивный" и "примитивно-рекурсивный". да, хрень какая-то. однако сама машина достаточно простая и хотя бы это уже меня радовало, когда я разбирался что это за фигня такая и зачем нам все это надо
Здравствуйте, Sharov, Вы писали:
S>Интересно, а формализовать многопроцессорную (многоядерную?) систему возможно?
Производители таких систем же как-то их проектируют и моделируют, у них этих формальных моделей целая пачка должна быть (с раными уровнями детализации).
Здравствуйте, dilmah, Вы писали:
D>Она корявая. Нормальные алгоритмы маркова, лямбда-исчисление и т.п. изящнее МТ.
Complexity вы на лямбдах упаритесь оценивать. Теорема Кука неспроста доказывается на МТ. Собственно все остальные формализации вычислимости ОЧЕНЬ далеки от реализации того, что у нас есть в железе. МТ тем и хороша, что на ней при всей её "неизящности" есть и модифицируемые состояния (привет лямбда-функциям) и разделение имён (номеров) ячеек от их значений (привет нормальным алгорифмам) и концепция времени как шага исполнения.
Здравствуйте, Sharov, Вы писали:
S>Интересно, а формализовать многопроцессорную (многоядерную?) систему возможно? S>Конечный автомат вряд ли получиться...
Разумеется, получится. Просто автомат этот будет недетерминированный, который маленьким комбинаторным взрывчиком превращается в детерминированный...
К>Разумеется, получится. Просто автомат этот будет недетерминированный, который маленьким комбинаторным взрывчиком превращается в детерминированный...
Вот, вот я о недетерминизме и подумал в первую очередь.
А под маленьким комбинаторным взрывчиком подразумевается описание всевозможных состояний процессоров
на данный момент?
Здравствуйте, Sharov, Вы писали:
S>А под маленьким комбинаторным взрывчиком подразумевается описание всевозможных состояний процессоров на данный момент?
Декартово произведение всех состояний, плюс декартово произведение всех переходов. Потому что из состояния <s1,s2,...> система может одномоментно совершить переход в <s1',s2,...>, в <s1,s2',...>, в <s1',s2',...> где s1->s1' — фрагемент КА первого процессора, s2->s2' — второго, и т.д., а <s1,s2,...> — состояние системы — кортеж состояний элементов.
На деле, разумеется, не все состояния доступны — как в силу недостижимости их вообще на данном процессоре ("если бы у рыб была шерсть"), так и из-за осмысленного взаимодействия процессоров.
Здравствуйте, Sharov, Вы писали:
S>Здравствуйте, Кодт, Вы писали:
К>>Разумеется, получится. Просто автомат этот будет недетерминированный, который маленьким комбинаторным взрывчиком превращается в детерминированный...
S>Вот, вот я о недетерминизме и подумал в первую очередь. S>А под маленьким комбинаторным взрывчиком подразумевается описание всевозможных состояний процессоров S>на данный момент?
Не спец.
Островок детерминированности в многопроцессорных системах — это память, общая (синхронизированная) для всех процессоров. Более сложный случай — NUMA архитектура. Но вроде в реальных нума-системах применяется специальная система синхронизации памяти (кешей). Дальше гомогенные сети, гетерогенные сети, ..., хаос.
Перекуём баги на фичи!
