Если любая вычислимая по Тьюрингу функция также вычислима в этом языке, то такой язык называют полным по Тьюрингу.
1. Если следовать этой логике, то полноту (не полноту) языка по Тьюрингу устанавливают для каждой, конкретной функции (либо их семейства). Так?
(То есть, сколько мы взяли функций, столько полнот (не полнот) языка по Тьюрингу и будет.)
2. И как по-вашему учесть, что "вычислимость (не вычислимость) по Тьюрингу" устанавливают для конкретной функции на конкретном автомате? (заметьте, в цитируемой странице написано "данная машина")
...и если кот Барсик по району "случайно блуждает", то мужик, вооружившись рыбой, идёт из любой точки района по кратчайшему пути к пивному ларьку. У них мир один, но разные вселенные.
Но фраза "алгоритм полон по Тьюрингу" не имеет совершенно никакого смысла. Полнота по Тьюрингу - это свойство вычислителей, то есть систем из "языка" и "исполнителя", в нашем смысле это язык программирования со своим компилятором и/или интерпретатором.
В общем, хороший рассказ, как инженеры катились тогда в верх... по наклонной.
...на нас подал в суд заказчик, которому мы не поставили в срок 20 компьютеров. Средств, чтобы повторно изготовить такое количество оборудования, у нас не было. Председатель нашего кооператива Михаил отбивался как мог. В итоге, в 1989 г наш кооператив "Визит" был закрыт. И для меня начались "темные времена"... Темные времена для меня наступили после закрытия нашего кооператива.Я остался без работы. Дело было еще в СССР. Не хотелось идти опять куда-то на службу, НИИ, или на завод. Меня туда уже не заманить никакими коврижками и пряниками.
Мой бывший компаньон и бывший председатель нашего кооператива Михаил Бурнусуз начал продавать несуществующие вагоны с углем, цистерны с нефтью. Потом занялся организацией автомастерской, которую через полгода закрыл из-за убытков. Стал торговать продуктами питания и т.д. и т.п. Короче, он стал обычным коммерсантом.
Вот и наступил он, последний день работы нашей фирмы в стенах пединститута. Как обычно, я работал не поднимая головы, т.к. клиенты стояли в очереди даже в институтском коридоре. Все наше имущество мы уже почти упаковали и работать в таких условиях было нелегко. Наступал вечер... Тут входит какой-то необычный клиент. Это было по нему сразу видно. Он предъявил мне корочки сотрудника соответствующего органа. Затем к нему присоединился другой сотрудник. Они написали большую бумагу, которую в соответствующих случая пишут. После этого забрали компьютер, на котором я работал. На следующий день я пришел в их контору, где вначале они еще раз меня припугнули, а затем попросили на разговор с начальством. Начальство по отработанной схеме сильно попросило у нас материальную помощь на развитие отдела в виде компьютерной техники. Все это было обставлено официальными бумагами. Я был очень добр и не в силах отказать. Тогда мой компьютер мне вернули, а через некоторое время мы оборудовали пару рабочих мест в их кабинетах компьютерами. Такие процедуры продолжались регулярно в течение многих лет. И приставали к нам не только они, но и несколько других уважаемых аналогичных контор с теми же вопросами помощи нашим славным защитникам. Иногда возникали даже коллизии, кому и в какую очередь мы "захотим" заниматься благотворительностью. Каждый такой жест "доброй воли" создавал огромную брешь в бюджете нашей небольшой фирмы.
Друзья, здесь не про "лучше-хуже" (как известно во всём есть множество +/-) и не про "нормальные языки", и не про "как можно сделать" а рассказ об аренах, и пример как их можно заюзать в AST. Демонстрация техники использования арен, только и всего. (Хоть, и не самая ясная.)
Ну, по образцу спецификации можно много чего записать (и формулы, и теоремы ...), а затем доказывать это. Форма записи, коей является ЛИ, - имеет к этому косвенное отношение.
И он точно доказал именно это? Проверенная информация? И вообще это докузуемо?
А то я пошарил по этому списку литературы, которая была под рукой и ничего такого там не нашёл.
Введение в математическую логику, т.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
"Лямбда-выражение" - по Вашей ссылке - это о другом. Вообще никакого отношения к Чёрчу не имеет.
А само "лямбда-исчисление" - не имеет никакого отношения к МТ. Ещё раз: ЛИ это просто спецификация в три строки, как оформлять функции. Смотрите эссе по ссылке выше.
(PS Наводящий вопрос: чем это отличается от конструкции процессора Intel 8086 либо Zilog Z80 либо Java VM ? Наводящий ответ: - ничем.
И таки-да: любой алгоритм, способный выполняться на этих процессорах ха-ха-ха... кхе-кхе... "полон по Тьюрингу".
Здесь разобрано в деталях
Императивные языки программирования имеющие if и goto реализуют Универсальную Машину Тьюринга. В том же 1936 году Алонзо Черч представил миру лямбда исчисление описанное тремя немудреными правилами о своих термах. https://habr.com/ru/articles/246139/
Хороший ответ. Но можно короче: "в 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.
1. Если следовать этой логике, то полноту (не полноту) языка по Тьюрингу устанавливают для каждой, конкретной функции (либо их семейства). Так?
(То есть, сколько мы взяли функций, столько полнот (не полнот) языка по Тьюрингу и будет.)
2. И как по-вашему учесть, что "вычислимость (не вычислимость) по Тьюрингу" устанавливают для конкретной функции на конкретном автомате? (заметьте, в цитируемой странице написано "данная машина")
...и если кот Барсик по району "случайно блуждает", то мужик, вооружившись рыбой, идёт из любой точки района по кратчайшему пути к пивному ларьку. У них мир один, но разные вселенные.
Да... в играх 1990-х есть 2 аспекта: технический и сисечный. Скучаем по обоим. :)
Может потому, что "теории как правильно писать код" уже вывели в период 30-60-х годов прошлого века?
Тогда прокомментируйте это:
Сострю: так переговоры шли эффективнее. :)
В общем, хороший рассказ, как инженеры катились тогда в верх... по наклонной.
Зацепило это:
:)
Друзья, здесь не про "лучше-хуже" (как известно во всём есть множество +/-) и не про "нормальные языки", и не про "как можно сделать" а рассказ об аренах, и пример как их можно заюзать в AST. Демонстрация техники использования арен, только и всего. (Хоть, и не самая ясная.)
Слабый заголовок. Я бы предложил:
Как кидануть наймита и загрести по-гуще бобла.
Когруэнтней будет. :)
Ну, по образцу спецификации можно много чего записать (и формулы, и теоремы ...), а затем доказывать это. Форма записи, коей является ЛИ, - имеет к этому косвенное отношение.
И он точно доказал именно это? Проверенная информация? И вообще это докузуемо?
А то я пошарил по этому списку литературы, которая была под рукой и ничего такого там не нашёл.
В курсе Мендельсона в главе Эффективная вычислимость на страницах 251-255 есть параграф "Алгорифмы Тьюринга", но там, насколько я понимаю, просто устанавливается изоморфизм над записью в некоторой формальной знаковой системе и МТ (поправьте, если не так).
PS Вообще алгебраисты - суровый народ со специфическим умом. Чтобы читать их книги нужно с малолетства, годами, вытренироваться алгебраистике, - иначе о каком-либо понимании можно забыть. Поэтому я как-то сторонюсь погружаться в чтение их книг. :)
Для разнообразия рекомендую попробовать
Уайтхед А.Н., Рассел Б. Основания математики. Том 1-3. 2005
:)
Нет, не путаю. Всё в точности как мной написано.
"Лямбда-выражение" - по Вашей ссылке - это о другом. Вообще никакого отношения к Чёрчу не имеет.
А само "лямбда-исчисление" - не имеет никакого отношения к МТ. Ещё раз: ЛИ это просто спецификация в три строки, как оформлять функции. Смотрите эссе по ссылке выше.
"Плаваете" в теме. "лямбда-исчисление" - это о другом.
Это простая спецификация в каком порядке писать функцию: где расставлять её аргументы, где писать тело и как отличить вызов функции от её определения.
Подробнее:
По машинам Тьюринга:
Что здесь не понятно?!
(PS Наводящий вопрос: чем это отличается от конструкции процессора Intel 8086 либо Zilog Z80 либо Java VM ? Наводящий ответ: - ничем.
И таки-да: любой алгоритм, способный выполняться на этих процессорах ха-ха-ха... кхе-кхе... "полон по Тьюрингу".
Здесь разобрано в деталях
)
Хороший ответ. Но можно короче: "в 1930-е изобретали вычислители ака "компьютеры". Машина Тьюринга - это спецификация стековой вычислительной машины."
А какие вычислители - от CPU и до VM-мок без стековой архитектуры?! :)
Как только подписался на правильных людей, сразу Хабр стал Торт!!!
>>Если вам понравилась статья — поставьте плюс, автору всегда приятно когда его работу ценят.
+/+/+/+
Ставлю плюс во все места (статью, карму, подписки, закладки)
>>Как известно, на машине Тьюринга (далее МТ) запрограммировать можно всё, что мы вообще считаем программируемым
А почему? И почему все так носятся с этими машинами Тьюринга?
Просвятите! ...ничего не понимаю :(
А можно ссылочку на репозиторий? А то статья из разряда "как я сделал", так ведь и посмотреть хочется...
искал тут, не нашёл
https://github.com/masscry?tab=repositories
Визуал мне понравился, а вот по механикам игры Coin-Op Vice у людей справедливо есть вопросы. :)
*
https://www.youtube.com/watch?v=KG9Hkvc0dD8
Норм контейнер. Позабавил и ЯП. Видна Рука Маэстро:
:)))
Выжимка основного от сюда
*
https://www.youtube.com/watch?v=cMR2c3vQRAc
Приятно видеть математику рядом с нейронками.
PS Та статья, которую поймёт лишь успешно прошедший курс дифференциальной геометрии и поля. :)
Приквел здесь: https://habr.com/ru/articles/906336/