Хабрахабр: Метки / тьюринг

Ненормальное программирование / Машина Тьюринга на чистом SQL

ncix — Fri, 04 Feb 2011 14:11:09 GMT

Пару месяцев назад прочитал пост, в котором уважаемая ksusha написала эмулятор машины Тьюринга используя MySQL и хранимые процедуры. Статья дала толчок к идее сделать машину Тьюринга на чистом SQL, без использования хранимых процедур. Для реализации был использован знакомый и любимый Firebird версии 2.1.

Существует две принципиальные проблемы при создании машины Тьюринга на голом SQL:

1) лента машины может быть и модифицирована и дописана, что требует операторов INSERT и UPDATE в одной конструкции;
2) машина Тьюринга требует как минимум одной переменной для состояния. Обычные SQL(DML)-запросы не могут хранить промежуточных переменных, по крайней мере в Firebird.

Тем не менее, мне удалось обойти эти ограничения

Читать дальше →

Ненормальное программирование / [Из песочницы] Эмулятор машины Тьюринга на MySQL

ksusha — Wed, 08 Dec 2010 20:10:06 GMT

Недавно на одном из собеседований мне задали задачку на разбор строки только средствами MySQL.
После этого я задумалась: а вообще, насколько сложные задачи такого рода можно решить с помощью одной лишь СУБД? Ответ нашелся быстро: средствами MySQL можно решить вообще любую задачу на распознавание строк. А чтобы делать это более удобным и универсальным способом, достаточно написать примитивный эмулятор конечного автомата, а еще лучше — машины Тьюринга, разумеется используя только лишь конструкции, любезно предоставляемые MySQL. Итак, начнем эксперимент.

Проектируем

Любая программа начинается с проекта. Так будет и в этот раз. Прежде всего, что такое машина Тьюринга, что она делает, что умеет? Умеет она, прямо скажем, немного. Имея в распоряжении бесконечную ленту и управляющее устройство (каретку) машина может:

Двигаться по ленте влево и вправо
Читать с ленты символ
Писать на ленту символ
Переходить в различные состояния

Читать дальше →

Персональные блоги / Любовь, мир и невычислимые функции

Ex3NDR — Tue, 05 Oct 2010 17:23:15 GMT

Давайте подумаем что такое знание в этом мире? И как это связано с любовью и Тьюрингом?

Читать дальше →

Научно-популярное / BBC: Тайная жизнь хаоса

EpiChild — Tue, 23 Mar 2010 18:46:37 GMT

Интересный документальный фильм BBC в котором профессор Джим Аль-Хэлили намеревается раскрыть одну из величайших тайн науки — что движет вселенную, которая начинается как пыль и в итоге заканчивается как разумная жизнь?
Просто и доступно доносятся очень глубокие, фундаментальные идеи о незаметной связи порядка и хаоса, природе нашего разума, внутренней способности вселенной к самоорганизации, происхождении человека и о многом другом. Русские субтитры.
1.

Смотреть дальше

IT-Биографии / Великобритания извиняется за смерть Алана Тьюринга

bubuq — Sat, 12 Sep 2009 00:05:15 GMT

Гордон Браун заявил, что сожалеет об «ужасном» отношении к Алану Тьюрингу, криптографу (математику, логику и основоположнику компьютерной науки) времён второй мировой войны, постигшему его как гея.

Онлайн-петиция на сайте «No 10» (Даунинг стрит 10 — резиденция премьер-министра) призывала правительство принести посмертные извинения первопроходцу ЭВМ.

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

Читать дальше →

Программирование / Для начала или вводный курс в эзотерический язык

Nuty — Thu, 20 Nov 2008 02:30:56 GMT

Это конечно же хобби, хотя...

Brainfuck придуман Урбаном Мюллером в 1993 году, в основном для забавы. Уникальный, вполне себе интересный Тьюринг-полный язык программирования с размером компилятора в 240 байт! В нём используется всего лишь 8 команд, каждая из них записывается одним символом. Программа на языке Brainfuck представляет собой последовательность этих самых команд.

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

Читать дальше →