2. Задача о матрицах, возникающая в теории автоматов

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

Каждая точка решетки имеет хорошо определенную систему соседних точек, и состояние точки в момент однозначно определяется состояниями всех ее соседей в момент Предполагая, что в момент активным является только конечное число точек, требуется выяснить, как будет распространяться эта активность. В частности, существуют ли «универсальные» системы, способные породить произвольные системы состояний. Существуют ли подсистемы, способные к «воспроизведению», т. е. к порождению подсистем, подобных исходной. В простом случае можно поставить вопрос так: существует ли бесконечная матрица из нулей и единиц такая, что для всех I, и обладающая тем свойством, что любая возможная конечная матрица из нулей и единиц является главным минором (стоящей на главной диагонали подматрицей) некоторой степени матрицы А. Положительный результат дал бы простой пример «универсальной» и «воспроизводящейся» системы (однако только в очень ограниченном смысле).

Аналогичный, но более общий вопрос может быть поставлен о матрицах, элементы которых являются вычетами по

Подобное же исследование является уместным в случае «рекурсивных функций». Можно ли получить все рекурсивные функции с помощью предписанного алгоритма, применяемого к конечному множеству таких функций? Более общий вопрос: можно ли все выражения в системе Гёделя

получить из конечного числа таких выражений с помощью конечного числа правил композиции-, осуществляемых в определенном порядке, т. е., например, применением двух операций в порядке, заданном некоторой последовательностью двух символов?

Может быть, существует логический аналог нашей универсальной матричной модели.