• Эмулятор машины Тьюринга на MySQL

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

    Проектируем

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

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