Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Category:

Машины Тьюринга и клеточные автоматы

Я тут понял, что наш Ом надо объяснять, начиная с элементарного - с игры "Жизнь" и машины Тьюринга.

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

Конечный автомат - это "программа", а лента - "данные". Но данные легко преобразовать в программу - есть так называемая универсальная машина тьюринга, в которой есть возможность "программу" записать на ленте в виде палочек и пробелов вместе с данными, а автомат будет "интерпретатором".

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

Палочки не обязательно могут быть палочками - в "Жизни" это клеточки. Мы записываем программу+данные в виде клеточек, затем эти клеточки "эволюционируют по правилам", и считываем результат тоже в виде растровой картинки из клеточек-пикселей. Есть варианты правил, при которых оказывается тоже можно использовать игровую доску как универсальный (но неэффективный) вычислитель. При наличии соответствующих устройств ввода-вывода, которые смогут преобразовать входные данные в клеточки, и из клеточек обратно получить "нормальные" данные - числа, строки, картинки, массивы, деревья...

Ом похож на такую доску - мы записываем входные данные и код в виде "выражения", оно "эволюционирует по правилам" в другое выражение, и мы это выражение обратно раскодируем в "нормальный" результат. Только роль пустых и заполненных клеточек играют звездочки, кванторы и лямбды. "На входе" у нас одни звездочки, кванторы и лямбды, а на выходе - другие.
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments