смотри, я собираюсь сделать такой язык программирования
у меня есть алфавит из четырех двух символов 0 и 1
состоянием программы является множество слов над алфавитом
программа это набор правил, которые рассматриваются по циклу
правило ::= (A, B, C, X)
если (множество содержит слово S, имеющее А префиксом) NAND (множество содержит слово B)
   выбрать из X
      0 : удалить слово S из множества
      1 : заменить в слове S префикс А на префикс C
      2 : добавить слово C в множество
это же функционально по Тьюрингу?