Рубрика «машина Тьюринга»

find + mkdir полны по Тьюрингу - 1

Введение

Мы покажем, что система, имеющая лишь команды GNU find и mkdir, полна по Тьюрингу.

Хорошо известно, что команды sed и awk сами по себе полны по Тьюрингу, но мне не удалось найти информации о Тьюринг-полноте find + mkdir.

Доказательство основано на реализации таг-системы.

Мы по порядку рассмотрим реализацию цикла, FizzBuzz и таг-системы.

Читать полностью »

Есть проблемы гораздо сложнее, чем NP-Complete - 1

Люди часто сравнивают P и NP в таком духе, что проблемы P простые, а NP — сложные. Но это чрезмерное упрощение. На самом деле проблемы могут быть намного, намного сложнее, чем NP.

В этом смысле можно вспомнить интеллектуально-фантастический триллер Travelling Salesman (Коммивояжёр, 2012) о четырёх математиках, нанятых правительством США для решения самой сложной проблемы в истории информатики — равенства классов сложности P и NP (P versus NP problem). И им это удалось. Чиновник министерства обороны США предлагает за их алгоритм вознаграждение $10 млн. Но сами математики слишком хорошо понимают, какие разрушительные последствия принесёт в мир их открытие. Один из лучших фильмов про математику в истории кинематографа…
Читать полностью »

Привет! В свободное от работы время по вечерам мне нравится воплощать в жизнь свои сумасшедшие идеи. В один из таких вечеров родилась мысль реализовать компилятор кода в машину Тьюринга. Осознав всю тщетность бытияЧитать полностью »

Машина Тьюринга в Doom - 1

DOOM (игра 1993 года для DOS) полон по Тьюрингу. Это значит, что можно запустить DOOM в DOOM. В статье приводятся подробности реализации.

Предисловие

Прежде чем углубляться в разработку, нужно дать немного контекста. Если вы имеете опыт программирования, то можете пропустить краткое описание понятия полноты по Тьюрингу.

Что такое полнота по Тьюрингу?

Итак, какую-то видеоигру можно назвать универсальной, полной по Тьюрингу или программируемой. Что это означает? По сути, это значит, что в этой игре можно реализовать компьютер. Но тут есть свои тонкости: если для этого игроку придётся делать слишком много, то это будет уже не так интересно.
Читать полностью »

Julia и клеточные автоматы - 1

Сегодня мы отправимся в красочное путешествие по миру клеточных автоматов, попутно изучая некоторые хитрые приемы их реализации, а также попытаемся понять, что скрывается за этой красотой — любопытная игра для праздного ума или глубокая философская концепция, находящая отклики во многих моделях.

Читать полностью »

Плитки (домино) Вана были изобретены Хао Ваном в 1961 году для математических задач, но нашли широкое применение в играх при создании тайловой графики. Благодаря им результаты не выглядят повторяющимися, как в 2D-текстурах, так и в 3D-моделях с тайлингом.

Похоже, что плитки Вана также способны исполнять машины Тьюринга, и следовательно, они Тьюринг-полны, а значит, могут выполнять любую программу.

Это удивительное и непонятное заявление, поэтому в данном посте я немного исследую этот вопрос.

Вкратце о плитках Вана

Плитки Вана — это прямоугольные тайлы, у которых каждая из граней может соответствовать только другим конкретным граням, но для любой конкретной грани есть несколько возможных тайлов, которые могут соответствовать этой грани. Под соответствием граней я подразумеваю, что они соединяются бесшовно, не создавая никаких визуальных артефактов и признаков наличия шва между тайлами.

Это полезное для графики свойство, потому что оно позволяет создавать бесшовную тайловую графику, но конфигурация расположения тайлов при этом может быть полностью рандомизирована при условии, что все грани совместимы друг с другом. В результате получается тайловая графика, которая совсем не похожа на повторяющуюся, потому что визуальные паттерны становятся гораздо менее заметными, чем у традиционной тайловой графики.

Графические примеры, более подробную информацию и ссылки на Shadertoy можно найти здесь: Wang Tiling.

Вот созданный мной пример. Моя графика — это «арт программиста», но надеюсь, идея понятна. Рисунок составлен из 16 тайлов, и для каждой грани есть два различных типа граней.

Плитки Вана для симуляции машин Тьюринга - 1

Читать полностью »

Книга Алана Тьюринга и загадочная записка — Научный детектив - 1
Оригинал перевода в моём блоге

Как ко мне попала эта книга?

В мае 2017 года я получил электронное письмо от моего старого учителя средней школы по имени Джордж Раттер, в котором он писал: «У меня есть копия большой книги Дирака на немецком языке (Die Prinzipien der Quantenmechanik), которая принадлежала Алану Тьюрингу, и после того как я прочел вашу книгу Создатели идей (Idea Makers), мне показалось само собой разумеющимся, что вы именно тот человек, которому она нужна». Он объяснил мне, что получил книгу от другого (к тому времени умершего) моего школьного учителя Нормана Рутледжа, о котором я знал, что он был другом Алана Тьюринга. Джордж закончил свое письмо фразой: «Если вам нужна эта книга, я мог бы вручить ее вам в следующий раз, когда вы приедете в Англию».

Спустя пару лет в марте 2019 года я действительно прибыл в Англию, после чего договорился с Джорджем о встрече за завтраком в небольшом отеле в Оксфорде. Мы ели, болтали и ждали, пока еда уляжется. Затем настал подходящий момент для обсуждения книги. Джордж сунул руку в портфель и вытащил довольно скромно оформленный, типичный академический томик середины 1900-х годов.

Книга Алана Тьюринга и загадочная записка — Научный детектив - 2

Я открыл обложку, размышляя, не может ли на ней быть с обратной стороны надписи: «Собственность Алана Тьюринга» или чего-то в этом духе. Но, к сожалению, это оказалось не так. Тем не менее к ней была приложена достаточно выразительная записка на четырех листах от Нормана Рутледжа к Джорджу Раттеру, написанная в 2002 году.

Я знал Нормана Рутледжа, когда еще был учеником средней школы в Итоне в начале 1970-х годов. Он был учителем математики по прозвищу «Чокнутый Норман». Он был приятным во всех отношениях преподавателем и рассказывал бесконечные байки о математике и о всяких других занимательных вещах. Он был ответственным за то, чтобы школа получила компьютер (программируемый с помощью перфоленты шириной с парту) — это был самый первый компьютер, который я когда-либо использовал.
Читать полностью »

На Тостере иногда встречаются вопросы о том, как научиться думать как программист. Год назад я ради развлечения решил написать программу которая решает всем хорошо известную задачку — головоломку о волке, козе и капусте. В англоязычных источниках известную как river crossing puzzle.

В этом посте я представлю вам пример мыслительного процесса от задачи к ee алгоритмическому решению.
Читать полностью »

Периодически на хабре можно встретить статьи о том, какие невероятные вещи можно сделать на шаблонах C++: конечные автоматы, лямбда-исчисление, машина Тьюринга и многое другое.

Параметризованные типы в Java традиционно считаются лишь пародией на шаблоны C++ (несмотря на то, что их даже сравнивать как-то некорректно), и причины этого несложно понять. Тем не менее не всё так плохо, и компилятор Java можно заставить производить во время проверки типов любые вычисления, лишь бы хватило оперативной памяти. Конкретный способ это сделать был описан в ноябре 2016-го года в этой прекрасной публикации. Его я и хотел бы объяснить.

Для затравки приведу следующий код. Корректен ли он? Предлагаю скомпилировать и проверить, угадали ли вы результат.

class Sample {

    interface BadList<T> extends List<List<? super BadList<? super T>>> {}

    public static void main(String[] args) {
        BadList<? super String> badList = null;
        List<? super BadList<? super String>> list = badList;
    }
}

Узнать ответ

Компилятор выбросит java.lang.StackOverflowError независимо от размера стэка.

Разберёмся, почему компилятор ведёт себя именно так (я бы не назвал это багом), как понимание данных причин может быть полезно и причём тут машина Тьюринга.

Читать полностью »

Размышления , о применение генетического алгоритма для Машина Тьюринга.

Есть некая информация получаемая из внешней среды, представленная в бинарном коде, и есть Машина Тьюринга. А что если, взять и применить генетический алгоритм для составления программы Машина Тьюринга.
Которая, в свою очередь, будет конвертировать определенные данные, и сравнивать результаты выполнения модифицированной программы с эталоном решения.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js