Рубрика «машина Тьюринга»
По заветам Макконнела
2026-08-19 в 20:41, admin, рубрики: esp32, qt, vs code, автоматное программирование, машина ТьюрингаЕсли вы начинающий программист и у Вас нет машины, то лучшее решение — машина Тьюринга (МТ)! Я в этом вам помогу, а еще Макконнел. Но и не только он один.
Первая моя статья на Хабре о машинах Тьюринга это про тяжелый грузовик [1]. А оно такое надо? Начинать лучше с чего‑то полегче. Этим и займемся. Хотя основа или, так сказать, базис по большому счету будет один. Но, ведь, между карьерным самосвалом и самой простой «инвалидкой» тоже есть много общего? И то и другое явно не самолет.
[AI ⊂ TM] Машина Тьюринга и искусственный интеллект
2025-12-31 в 10:15, admin, рубрики: neural network, Q-learning, reinforecement learning, turing machine, генетические алгоритмы, генетическое программирование, машина Тьюринга, нейронная сетьПререквизиты
Обязательно - основы теории вычислений, искусственные нейронные сети.
Желательно - генетические алгоритмы, RL-агенты.
Почему машина Тьюринга?
Действительно, почему машина Тьюринга (TM) сегодня в теме про искусственный интеллект (AI) ? Ведь AI сегодня это все больше про машинное обучение (ML), искусственные нейронные сети (Читать полностью »
Настольные игры для юных программистов и робототехников. Что можно купить в 2025 году?
2025-08-24 в 17:10, admin, рубрики: битва големов, М.А.Р.И, машина Тьюринга, настольные игры, образование детей, Программирование, робототехникаНаучные настольные игры продолжают оставаться достаточно специализированной нишей, балансируя на грани между «обычными» настольными играми и методическими пособиями. Я решил рассказать о наиболее интересных новинках с обучающим уклоном в информатику, программирование и робототехнику, доступных в России в 2025 году.
Критерии отбора были следующие:
-
Игра должна быть образовательной или иметь научную тематику в части информатики, программирования или робототехники;
-
Игра должна быть выпущена в России или локализована на русском языке;
Реализм против платонизма. Неполнота Гёделя, неразрешимость Тьюринга и физические основания математики
2025-07-08 в 10:51, admin, рубрики: квантовый компьютер, машина Тьюринга, основания математики, платонизм, проблема остановки, проблема разрешимости, тезис Чёрча-Тьюринга, теорема Гёделя, теория множеств
Об одном красивом неизвестном решении одной известной задачи
2025-05-14 в 14:00, admin, рубрики: Алгоритмы, машина Тьюринга
find + mkdir полны по Тьюрингу
2024-08-20 в 10:55, admin, рубрики: find, fizzbuzz, GNU, mkdir, машина Тьюринга, полнота по Тьюрингу, Регулярные выражения
Введение
Мы покажем, что система, имеющая лишь команды GNU find и mkdir, полна по Тьюрингу.
Хорошо известно, что команды sed и awk сами по себе полны по Тьюрингу, но мне не удалось найти информации о Тьюринг-полноте find + mkdir.
Доказательство основано на реализации таг-системы.
Мы по порядку рассмотрим реализацию цикла, FizzBuzz и таг-системы.
Есть проблемы гораздо сложнее, чем NP-Complete
2023-06-06 в 8:01, admin, рубрики: crypto, np, np-complete, np-hard, NP-полная задача, p=np, PSPACE, timeweb_статьи, Алгоритмы, Блог компании Timeweb Cloud, задача тысячелетия, информационная безопасность, класс NP, классы сложности, криптография, математика, машина Тьюринга, теоретическая информатика, теория алгоритмов, теория вычислимости
Люди часто сравнивают P и NP в таком духе, что проблемы P простые, а NP — сложные. Но это чрезмерное упрощение. На самом деле проблемы могут быть намного, намного сложнее, чем NP.
В этом смысле можно вспомнить интеллектуально-фантастический триллер Travelling Salesman (Коммивояжёр, 2012) о четырёх математиках, нанятых правительством США для решения самой сложной проблемы в истории информатики — равенства классов сложности P и NP (P versus NP problem). И им это удалось. Чиновник министерства обороны США предлагает за их алгоритм вознаграждение $10 млн. Но сами математики слишком хорошо понимают, какие разрушительные последствия принесёт в мир их открытие. Один из лучших фильмов про математику в истории кинематографа…
Читать полностью »
Симулятор x86 подобного процессора на машине Тьюринга
2022-05-15 в 13:05, admin, рубрики: javascript, turing machine, Алгоритмы, машина Тьюринга, Программирование, симулятор процессораПривет! В свободное от работы время по вечерам мне нравится воплощать в жизнь свои сумасшедшие идеи. В один из таких вечеров родилась мысль реализовать компилятор кода в машину Тьюринга. Осознав всю тщетность бытияЧитать полностью »