Comments 19
Человек, поставивший мне минус в карму за "распространение рекламы" после публикации этой статьи, объясни, пожалуйста, своё действие! Это воспринимается как реклама инициальных детерминированных конечных автоматов?
Единицы в карме не жалко, но хотелось бы понять логику.
Я точно не тот человек, который поставил Вам минус. Да и вообще с появлением функции "скрыть публикации автора" считают механизм кармы - рудиментом (не хочешь - не читай). Но в данной статье Вы продемонстрировали "плавание" и кролем, и брасом, и буттерфляем. А о "выводах" я просто помолчу.
Ничего не имею против "методичек" из "центра Европы", но желающим разобраться в вопросе рекомендовал бы заглянуть в англоязычную Википедию. Где одна простая ясная картинка полно и исчерпывающе человеческим языком разъясняет суть МТ.
Сейчас я опущу математику - то есть не буду строго описывать МТ через кольца, поля, алгебры... - ни к чему это. А просто поясню суть картинки. Это оболочковая модель.
1. Оболчка Вычислительное Ядро ("combinational logic") - это реализация операций (плюс, умножить, поделить, итд всё что вы напридумываете), они "сидят" в "головке" ТМ.
2. Следующая оболочка: finite-state machine (FSM) - это описание пространства состояний устройства банальнй дискретной математикой ( можно описывать так https://ru.wikipedia.org/wiki/Отношение_(теория_множеств) , а можно и так https://ru.wikipedia.org/wiki/Граф_(математика) - в данном случае это дело вкуса, описания будут эквивалентны ).
3. Следующая оболочка: pushdown automaton ( PDA ) или магазинный автомат — это тип автомата , использующий стек . Да, да, друзья, пресловутая "лента" по которой" "ездит" головка с песловутыми командами МТ "перейти влево/вправо", "считать/записать в ячеку ленты" - это реализация стека с командами "push/pop".
4. Следующая оболочка"Turing machine", означает, что совокупно конструкцию, описанную в пунктах 1-3 называют "Машина Тьюринга". Алгоритмы, которые могут вычисляться на конкретной МТ, называются "вычислимыми по Тьюрингу" для данной машины (ибо см. пункт №1 - вычислительные операции у разных машин могут быть разные).
Можно спорить о "конечности" либо "бесконечности" ленты - но это сугубо софистические споры, ибо ничего в практику они не дают.
А практика в следующем.
Наводящий вопрос: чем это устройство отличается от конструкции/работы процессора Intel 8086? либо Zilog Z80? либо Java VM ? Наводящий ответ: - ничем. А практика в том, что в 1940-х, шла разработка вычислительных машин, и МТ - это и есть формальное описание архитектуры таких машин.
PS Кому интересно здесь ещё немного о "лямбда исчислении" со ссылкой на моё эссе о нём.
https://habr.com/ru/articles/909162/comments/#comment_28330782
впринципе все правы, ведь ассемблер Тьюринг полный написав переходы по максимально доступному числу вы получите переходы по максимально доступному числу, и вся система должна поддержать это число иначе просто переходы не будут доступны, соответственно всё скатится у Тьюринг машины к организации памяти поидее, тоесть регистр-регистр, регистр - память )
https://godbolt.org/z/PrscerjvY
системы отличаются работой с памятью как раз
у интела одно число и набор комманд - кристалл, у явы сферическая своя - приводит к организации памяти, у зилога предположу так же, тоесть входные данные зависят от кристала или виртуального кристала типо, тоесть у кристала или виртуальной системы входные параметры это сам кристал и он как саппорт для переходов по максимально доступному числу, а это явная(а может и неявная) связь и подвязка к организации памяти
Поторопились Вы с ответом а может поленились пройти по ссылочке? Помимо ссылки на упомянутое эссе
своего рода моё эссе о Лямбда-Исчислении.
https://habr.com/ru/articles/767864/comments/#comment_26107578
там есть ещё ссылка на эту замечательную статью от 2014 года с хабра:
Здесь разобрано в деталях
Императивные языки программирования имеющие if и goto реализуют Универсальную Машину Тьюринга. В том же 1936 году Алонзо Черч представил миру лямбда исчисление описанное тремя немудреными правилами о своих термах.
https://habr.com/ru/articles/246139/
*
И ещё, что не маловажно, там есть список книг на русском с первоисточниками по теме (да, да, с Самим Чёрчем :).
ну правильно потомучто переход это ключ к понимаю что происходит а полнота это максимальное число в системе, соотв это не только переходы, но и память, приведу пример
тоесть 65 тыщ if - else или 1 if и map
спасибо перейду - посмотрю
Императивные языки программирования имеющие if и gotoреализуют Универсальную Машину Тьюринга
Это большое упрощение. В вузе так действительно учат для простоты, но это не совсем правда, что и разбирается в данной статье.
Что в статье разбирается - для меня - загадка.
Я конечно, понял, что интуитивно и наивно Вы пытались сделать: определить и просчитать пространство состояний дискретного автомата. Но как математическую задачу можно браться решать без математики - это загадка ещё по хлеще будет.
Да и математики той нужно было лишь начала элементарой теории множеств (выбрать множества, определить отношения над ними, взять декартово произведение, посчитать мощности множеств).
Кстати, пользуясь случаем. Никогда не интересовался и не вдавался в вопрос что значит не менее загадочная, и даже из-за частоты упортреблений, не побоюсь этого слова, сакральная фраза "язык программирования полный по Тьюрингу"? Что на данном ЯП-е можно реализовать МТ? либо она имеет иной смысл?
Я конечно, понял, что интуитивно и наивно Вы пытались сделать: определить и просчитать пространство состояний дискретного автомата
Совсем не так. Пространство состояний дискретного автомата очевидно, чего его считать? Это типовая задачка для 2 курса.
Я пытался объяснить, какая вычислительная и семантическая модель является адекватной для реального компьютера и реальной программы.
Кстати, пользуясь случаем. Никогда не интересовался и не вдавался в вопрос что значит не менее загадочная, и даже из-за частоты упортреблений, не побоюсь этого слова, сакральная фраза "язык программирования полный по Тьюрингу"? Что на данном ЯП-е можно реализовать МТ? либо она имеет иной смысл?
В просторечии тут имеется в виду, что язык равномощен мТ в вычислительном смысле, то есть что всякий алгоритм вычислим при помощи мТ тогда и только тогда, когда он вычислим при помощи некоторой программы на данном языке. А ещё проще говоря – что на этом языке можно запрограммировать любой алгоритм, программируемый при помощи других языков и, в частности, машины Тьюринга. В частности, в силу самоприменимости машины Тьюринга, это означает и то, что на языке можно реализовать мТ.
Если же говорить строго, то надо к этому добавлять: “... если пренебречь объёмом памяти”.
Не обижайтесь, но Вы сейчас изложили по учебнику очевидные вещи, которые проходят на 2 курсе (я предполагал знание этой базы пререквизитом для чтения данной статьи, и просто напомнил несколько формальных определений). И притом ухитрились сделать неверный вывод, так как именно бесконечность ленты в машине Тьюринга принципиальна. Настолько принципиальна, что конечный автомат даже специально называется конечным.
Кроме того, замечу, что вычислимость по Тьюрингу для разных машин (без оракула) эквивалентна между собой. В этом и сила.
Что касается лямбда-исчисления, то это та же мТ, вид сбоку. Кто и на каких основаниях должен делать редукции? Это просто формализм для процесса вычислений, как он представляется одурманенному гормонами мозгу человека.
Покажите мне лямбда-редуктор или мТ в природе. Таких нет, это конструкция ума. А регулярная порождающая грамматика - это любая химическая реакция, например.
Методически же не очень верно пытаться опровергнуть материал с уровнем "сложный" цитатами из Википедии.
окей но тогда на текущий момент есть Тьюринг Risc, Risc-V и Cisc и другие
и в таких Тьюрингах какие есть придётся уже смотреть как организована работа с памятью и какой тип в основном регистр-регистр или иная, какое число, какой форм фактор, тех процесс, какие комманды и тд
как организовать проход до максимума полного тьюринга если система на практике посыпется из-за неподдержки максимального числа, тоесть памяти нет, число максимальное не держится на системе, какой это тьюринг тогда
значит Тьюринг это такая система которая может организовать полный комплексный проход до максимального(хотябы своего же числа) если она и этого не сможет сделать то это не понятный какой-то Тьюринг,
в контексте бесконечности, она то бесконечная, но внутри Тьюринг системы должен быть механизм утилизации и он обычно есть иначе не было бы природы переходов
Тьюринг это такая ситуация когда есть система Тьюринг она предоставляет бесконечность прохода данных на конечном заданном отрезке
все отрезки могут быть тоже Тьюрингами просто программист сделал конечный автомат и Тьюринг родитель предоставляет эту ситуацию
Любая конкретная процессорная архитектура, если говорить совсем строго, не имеет полноты по Тьюрингу из-за ограниченности адресуемой памяти. Абстрактный язык программирования может иметь, а может не иметь. Реализация языка программирования никогда не имеет, так как опирается на процессорную архитектуру.
Разница между аппликацией и вызовом функции у меня разобрана здесь.
Честно говоря я не совсем понял смысла статьи, но вижу что автору хочется пофилософствовать и, пожалуй, поддержу. :)
Как мне кажется Вы несколько ошиблись в определении компьютера запихнув в него память. Компьютер (вычислитель) это конечный автомат отделенный от памяти, так написано в книжках и так всегда учили в ВУЗе. У вычислителя есть своя внутрення память - регистры и различные флаги. И именно их совокупным состоянием определяется число состояний автомата-вычислителя. Условно, у MOS 6502 есть регистры A[7:0], X[7:0], Y[7:0], SP[7:0], PC[15:0] и F[6:0], всего - 55 бит (на самом деле там есть еще программно невидимые регистры, но не в этом суть). Итого 3.6028797019e+16 сосотяний из которых далеко не все являются валидными (в некоторые состояния автомат не может перейти). Память же это источник внешних событий и способ сохранения результата работы автомата, но не его часть. Рассматривать вычиситель+память как конечный автомат тоже можно, но зачем ? В этом нет никакого смысла.
Мы же пишем программы для процессора вместе с памятью, а не отдельно от неё. Переменные программы хранятся в памяти. Одна и та же команда процессора, скажем, LDA 10 даст разный результат в зависимости от содержимого памяти по адресу 10. Это даст нам недетерминированный конечный автомат, который ничего не даёт в смысле разговоров об алгоритмах и вычислимости.
Если мы будем рассматривать состояния только самой микросхемы 6502, то для детерминированности тогда и программы надо писать без использования обращений к памяти, а на четырёх регистрах общего назначения (включая SP, который в таком случае будет просто теневой копией X) много не насчитаешь.
В машине Тьюринга память представляется бесконечной лентой.
Идея заключается как раз в том, что, если отделить процессор от памяти, то он представляется каким-то одушевлённым существом, имеющим собственное поведение и реагирующим на события окружающего мира. В то время как вместе с окружением в виде памяти это просто банальный итератор по линейной последовательности состояний.
*** Спасибо, кстати, я увидел, что в статье ошибочно регистр PC обозвал SP :) Исправил.
Ну вот я детям пытаюсь обьяснить работу машины на примере TD4 - там всего четыре 4-х битных регистра и ПЗУ на переключателях. У этого автомата всего 65536 состояний и память их число не увеличивает. Такое редуцированное представление автомата гораздо проще понять. Как только Вы вводите ОЗУ, всё становится слишком сложно. :)
С точки зрения семантики, т.е. понятности для человека, декомпозиция действительно удобна.
значит может быть 65536 переходов если получать число и сравнивать с числами до 65536
поместить в а 65255
и сравниваем с числами до 65536
jeq 1
jeq 2
jeq 3
...
jeq 65536
и на каждый в это время будет выполняться своя метка разве нет?
ну и регистр-регистр регистр-память будет иметь разницу как раз
поидее как раз из-за того что состояние может быть только 1 в момент проверки тоесть мы переходим в 1 метку конкретно, значит должна быть организована ситуация по организации до 65536 чтобы была даже возможность хранить такие числа и соотв сравнить, изза того что переход 1 процессор как бы сделает утиль всего что скипает, и будет работать с тем выбранным регистром где число. в дальнейшем это кстати приведёт к 1 ответу что тоже логично
спасибо очень интересно, FLOPS там еще надо смотреть на организацию по работе с памятью регистр-регистр или загрузка в память,
приведу пример 3 тыщи if - else звучит страшно, но давайте подумаем, альтернатива это загрузка в память ) сам недавно переосмыслил для себя это)
Конечный автомат, машина Тьюринга, порождающая грамматика и компьютер: в чём разница