Comments 19
>>Если вам понравилась статья — поставьте плюс, автору всегда приятно когда его работу ценят.
+/+/+/+
Ставлю плюс во все места (статью, карму, подписки, закладки)
>>Как известно, на машине Тьюринга (далее МТ) запрограммировать можно всё, что мы вообще считаем программируемым
А почему? И почему все так носятся с этими машинами Тьюринга?
Просвятите! ...ничего не понимаю :(
Что вообще стоит считать алгоритмом? Сейчас в любом языке программирования присутствуют циклы и условные операторы, этого нам хватает для повседневности. Но вдруг мы могли бы добавить какую-нибудь хитрую операцию, которая позволила бы вычислять то, что без неё мы посчитать не сможем? Вот примерно таким же вопросом задавались математики 30-ых годов прошлого века, только вот у них на руках даже не было хоть какого-то единого понятия алгоритма, только какие-то отдельные применяемые в физике/математике методы. И вот тогда придумали
Лямбда-исчисление
Рекурсивные функции
Машину Тьюринга
Которые были +- эквивалентны и сводились к ключевому тезису "Все, что мы умеем вычислять может быть сведено к программе на машине Тьюринга". За почти 100 лет более полной модели вычислений так и не придумали, поэтому машина Тьюринга вошла в фундамент компьютерных наук. В современности она в большей степени является теоретическим инструментом -- например с её помощью формулируется проблема P и NP, на практике же мы все время пользуемся эквивалентами машины Тьюринга -- языками программирования (полные по Тьюрингу языки). Вот и суть как раз в том, что машина Тьюринга интересна с точки зрения теории и истории компьютерных наук, но на практике совершенно бесполезна, возможность решить какую-то осмысленную задачу небольшой машиной Тьюринга -- в этом есть определенная красота, но скорее всего никакой практической ценности.
Хороший ответ. Но можно короче: "в 1930-е изобретали вычислители ака "компьютеры". Машина Тьюринга - это спецификация стековой вычислительной машины."
А какие вычислители - от CPU и до VM-мок без стековой архитектуры?! :)
A Turing machine is equivalent to a single-stack pushdown automaton (PDA) that has been made more flexible and concise by relaxing the last-in-first-out (LIFO) requirement of its stack. In addition, a Turing machine is also equivalent to a two-stack PDA with standard LIFO semantics, by using one stack to model the tape left of the head and the other stack for the tape to the right.
At the other extreme, some very simple models turn out to be Turing-equivalent, i.e. to have the same computational power as the Turing machine model.
считаю нужным отметить, что машины Тьюринга неспроста стали основной теоретической моделью вычислений.
можно поспорить о том, что МТ проще и/или изящнее. но дело не в этом. в отличие от двух упомянутых альтернатив, МТ совершенно естественно позволяет математически определить используемые программой ресурсы - время и память. это ровно то, что позволило в то время сменить парадигму теории вычислений.
в МТ используемая память оценивается самой дальней позицией головки. сравните с лямбда-исчислением - попробуйте придумать, как там оценить используемую алгоритмом память :)
к современным компьютерам модель МТ, по-моему, подходит всё ещё удачно. основное отличие - в современных компьютерах у нас имеется (почти) произвольный доступ к (почти) произвольным ячейкам памяти.
"Плаваете" в теме. "лямбда-исчисление" - это о другом.
Это простая спецификация в каком порядке писать функцию: где расставлять её аргументы, где писать тело и как отличить вызов функции от её определения.
Подробнее:
своего рода моё эссе о Лямбда-Исчислении.
https://habr.com/ru/articles/767864/comments/#comment_26107578
По машинам Тьюринга:
Что здесь не понятно?!
(PS Наводящий вопрос: чем это отличается от конструкции процессора Intel 8086 либо Zilog Z80 либо Java VM ? Наводящий ответ: - ничем.
И таки-да: любой алгоритм, способный выполняться на этих процессорах ха-ха-ха... кхе-кхе... "полон по Тьюрингу".
Здесь разобрано в деталях
Императивные языки программирования имеющие if и goto реализуют Универсальную Машину Тьюринга.
В том же 1936 году Алонзо Черч представил миру лямбда исчисление описанное тремя немудреными правилами о своих термах.
https://habr.com/ru/articles/246139/
)
Это простая спецификация в каком порядке писать функцию: где расставлять её аргументы, где писать тело и как отличить вызов функции от её определения.
Мне кажется вы путаете лямбда-исчисление и лямбда-выражения. Последние вдохновлены первыми, но все-таки являются синтаксическим сахаром, а первое как раз про эквивалентное МТ функциональное представление алгоритмов.
Нет, не путаю. Всё в точности как мной написано.
"Лямбда-выражение" - по Вашей ссылке - это о другом. Вообще никакого отношения к Чёрчу не имеет.
А само "лямбда-исчисление" - не имеет никакого отношения к МТ. Ещё раз: ЛИ это просто спецификация в три строки, как оформлять функции. Смотрите эссе по ссылке выше.
ЛИ это просто спецификация в три строки, как оформлять функции. Смотрите эссе по ссылке выше
Если речь идет об этом комментарии -- написано забавно и интересно, Ваша трактовка имеет право на существование, но как будто в ней теряется огромный объем работы, проделанный Алонсо Черчем поверх этой, как вы это называете, спецификации. В частности например доказательство утверждения, что любое лямбда-выражение (в контексте лямбда-исчисления, а не современных языков программирования) можно вычислить на МТ и наоборот.
Ну, по образцу спецификации можно много чего записать (и формулы, и теоремы ...), а затем доказывать это. Форма записи, коей является ЛИ, - имеет к этому косвенное отношение.
И он точно доказал именно это? Проверенная информация? И вообще это докузуемо?
А то я пошарил по этому списку литературы, которая была под рукой и ничего такого там не нашёл.
Введение в математическую логику, т.1. - А.Черч.pdf
Клини С. Математическая логика. 1973.djvu
Колмогоров А.Н., Драгалин А.Г. - Введение в математическую логику - 1982.djvu
Мендельсон - Введение в математическую логику. 1971.djvu
Мендельсон Э. Введение в математическую логику - 1976.djvu
Попов А.И. - Введение в математическую логику - 1959.djvu
Зюзьков В.М. - Введение в математическую логику (Учебники для вузов. Специальная литература) - 2022.pdf
Mendelson E. - Introduction to Mathematical Logic, 6th edition (Textbooks in Mathematics) - 2015.pdfВ курсе Мендельсона в главе Эффективная вычислимость на страницах 251-255 есть параграф "Алгорифмы Тьюринга", но там, насколько я понимаю, просто устанавливается изоморфизм над записью в некоторой формальной знаковой системе и МТ (поправьте, если не так).
Мы можем теперь с каждой машиной Тьюринга Т связать некоторый алгорифм 3 в алфавите А машины Т.
с 252
PS Вообще алгебраисты - суровый народ со специфическим умом. Чтобы читать их книги нужно с малолетства, годами, вытренироваться алгебраистике, - иначе о каком-либо понимании можно забыть. Поэтому я как-то сторонюсь погружаться в чтение их книг. :)
Для разнообразия рекомендую попробовать
Уайтхед А.Н., Рассел Б. Основания математики. Том 1-3. 2005
:)
И он точно доказал именно это? Проверенная информация? И вообще это докузуемо?
Это совместное творчество Чёрча, Тьюринга, Гёделя и Клини и возможно других, +- хорошо на вики написано про историю вопроса
https://ru.wikipedia.org/wiki/Тезис_Чёрча_—_Тьюринга#История
"Плаваете" в теме.
Представьте себе, лямбда-исчисление не зря называется "исчисление". Лямбда-исчисление задаёт такую же систему, как, например, язык Python и его интерпретатор. Представьте себе, любую программу на Python, которая вычисляет натуральное f(x) по x, можно записать в виде лямбда-выражения! Это и есть "программный код" в современном смысле. С помощью правила бета-редукции вы уже "исполняете" этот самый программный код.
Для вас же сейчас очевидно, что МТ - это совсем понятное описание компьютера, а лямбда-исчисление, как вам кажется, "просто способ записи функций". Но это не так. Это альтернативы описания одного и того же. В современном понимании - "программ" и их "исполнителей".
Что тут непонятного?!
В том и дело, что Чёрч, Тьюринг и другие рассуждали о вычислениях ещё до появления компьютеров, то есть, "автоматических вычислителей". Они пытались формализовать концепцию того, что, грубо говоря, можно вычислить на бумаге за конечное число шагов, следуя некоторому конечному простому набору правил из простейших манипуляций. Как, например, алгоритм Евклида. Таким процессам не было чёткого формального определения.
Как описать все функции, которые можно вот так вот, "на листочке", согласно "простым правилам" вычислить за конечное число шагов? Этот вопрос учёные и пытались решить ещё до появления компьютеров. Им было это совсем ещё не понятно.
Как оказалось, они придумали альтернативные описания одного и того же. Я вижу, что ниже уже предложили почитать про тезис Чёрча-Тьюринга, я дополню, что в английской википедии более детально изложено, рекомендую почитать.
И таки-да: любой алгоритм, способный выполняться на этих процессорах ха-ха-ха... кхе-кхе... "полон по Тьюрингу".
Да, вы правильно понимаете, что обсуждаемые нами вещи напрямую связаны с Тьюринг-полнотой. Но фраза "алгоритм полон по Тьюрингу" не имеет совершенно никакого смысла. Полнота по Тьюрингу - это свойство вычислителей, то есть систем из "языка" и "исполнителя", в нашем смысле это язык программирования со своим компилятором и/или интерпретатором. Полнота по Тьюрингу означает, что на языке программирования можно записать любую программу, которая записывается в машинах Тьюринга. Или в лямбда-исчислении Чёрча. Или в общерекурсивных функциях Гёделя. И, в обратную сторону, программу на вашем полном по Тьюрингу языке можно переписать в машину Тьюринга или в программу лямбда-исчисления.
Если откорректировать ваше высказывание, то оно будет звучать как "Любую программу, которую способны выполнить эти процессоры, можно переписать в машину Тьюринга". Вы можете удивиться, но можно даже построить одну машину Тьюринга (зависящую лишь от архитектуры процессора), которая на вход будет ещё принимать машинный код (ассемблер) этой самой программы, и будет исполнять его так, как надо. Таким образом, машина Тьюринга становится исполнителем, а язык программирования - не меняется. В этом плане процессоры, конечно, менее мощны вычислительно, чем машины Тьюринга, с точки зрения математики - у них конечная память =)
Но фраза "алгоритм полон по Тьюрингу" не имеет совершенно никакого смысла. Полнота по Тьюрингу - это свойство вычислителей, то есть систем из "языка" и "исполнителя", в нашем смысле это язык программирования со своим компилятором и/или интерпретатором.
Тогда прокомментируйте это:
Так здесь вычислимость, а не полнота. Собственно функция может быть или не быть вычислима по Тьюрингу. Если любая вычислимая по Тьюрингу функция также вычислима в этом языке, то такой язык называют полным по Тьюрингу.
Если любая вычислимая по Тьюрингу функция также вычислима в этом языке, то такой язык называют полным по Тьюрингу.
1. Если следовать этой логике, то полноту (не полноту) языка по Тьюрингу устанавливают для каждой, конкретной функции (либо их семейства). Так?
(То есть, сколько мы взяли функций, столько полнот (не полнот) языка по Тьюрингу и будет.)
2. И как по-вашему учесть, что "вычислимость (не вычислимость) по Тьюрингу" устанавливают для конкретной функции на конкретном автомате? (заметьте, в цитируемой странице написано "данная машина")
Попробую переформулирвать. Если все вычислимые по Тьюрингу функции также вычислимы и в неком языке, то этот язык полон по Тьюрингу. Здесь фигурирует только один конкретный класс функции -- вычислимых по Тьюрингу.
Возможно есть недопонимание в терминологии, да и книга старая. Я уверен, что "данная машина" в контексте -- это собственно программа на МТ, т.е. набор состояний и правил перехода. Вычислимость не определяется для конкретной программы, имеется в виду, что если мы нашли программу, которая вычисляет функцию, то эта функция вычислима
1. Не бывает "всех вычислимых по Тьюрингу функций": у каждой МТ в головке зашит свой набор правил, поэтому, что одна машина может делать - другая уже не может.
Пример: делаем автомат для булевой логики - и всё, все, функции, несоводимые к ней - "не вычислимы по Тьюрингу" для данного автомата. Так что я не понимаю и не принимаю о каких "всех вычислимых по Тьюрингу функциях" идёт речь.
2. "Книга старая" - это вообще аргумент из области стендапа. Выше Вы послали меня на/в "энциклопедию для народа" - педИю (хорошо, что ещё не в/на "Интернет"), которая сама, конечно, если верить заявленым её учредителям целям, цитирует работы Чёрча, Тьюринга и иных - то есть так называемые "старые книги" (которые я цитирую, со ссылками на страницы, кстати). Предлагаю оставить подобную риторику для бедных - конечно, бедных интеллектуально и духовно, - и больше не возвращаться к ней.
у каждой МТ в головке зашит свой набор правил, поэтому, что одна машина может делать - другая уже не может
Хорошо, в этой терминологии функция вычислима, если существует МТ, которая на любых входных данных останавливается и результатом является значение функции. Соответственно каждая машина Тьюринга задает какую-то вычислимую функцию. Множество таких функций и есть "все вычислимые по Тьюрингу функции"
"Книга старая" - это вообще аргумент из области стендапа
"Книга старая" относилось исключительно к тому, что со временем так или иначе меняется терминология и, в частности, понятие "полноты по Тьюрингу" могло раньше не использоваться, в частности в книге Клини я его не нашел. Зато буквально через несколько страниц там написано ровно то, что я писал ранее
и еще вот
Хорошо, в этой терминологии функция вычислима, если существует МТ, которая на любых входных данных останавливается и результатом является значение функции. Соответственно каждая машина Тьюринга задает какую-то вычислимую функцию.
С этим согласен, оч. хорошее наблюдение.
Но мы же "пляшем" не от автоматов, а от функций: у нас есть математика+ и мы под неё конструируем вычислитель. А строгать автоматы, которые вычисляют "какую-то вычислимую функцию", затем изучать а что это за функция, - в аспекте обучения моделированию - это и неплохо: "построй по автомату функцию". Но мы то обсуждали не Reserarch в R&D, а обратный ход: когда Reserarch готов, и мы реализуем его в Development.
PS За дискуссию спасибо, она была небезынтересной!
Так исторически сложилось. Когда Тьюринг занимался разработкой теории он пришёл к тому, что любую программу можно выразить сначала в виде лямбда исчисления, а потом уже доказал, что тьюринг машина фактически этому тождественна, ну а там уже и свой ломатель Энигмы поставил на эти рельсы.
Об одном красивом неизвестном решении одной известной задачи