Pull to refresh
57
Karma
0
Rating
Ксюша @ksusha

User

  • Followers 10
  • Following 7

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

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

Проектируем

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

Читать дальше →
Total votes 71: ↑61 and ↓10 +51
Views 10K
Comments 23

Information

Rating
Does not participate
Location
Москва, Москва и Московская обл., Россия
Works in
Date of birth
Registered
Activity