436
правок
Изменения
м
Самовоспроизводящиеся клеточные автоматы: punctuation
## Какой класс автоматов может быть построен каким-то автоматом?
# Конструктивная универсальность.
## Существует ли конструктивно универсальный автомат ? (т. е. автомат, способный построить любой автомат)?
# Самовоспроизведение.
## Существует ли самовоспроизводящийся автомат?
## Существует ли автомат, который , помимо самовоспроизведения , может решать и другие задачи?
# Эволюция.
## Может ли при конструировании автомата автоматом происходить усложнение типа автомата?
## Может ли такая эволюция происходить в направлении от менее эффективного к более эффективному автомату ? (при надлежащем определении понятия эффективности)?
Тьюринг показал, что предложенный им класс автоматов логически универсален, т. е. автоматы Тьюринга могут выполнить произвольный логический процесс (произвольное вычисление), если их снабдить конечным, но сколь угодно продолжаемым запоминающим механизмом (памятью). Тьюринг показал также, что существует универсальная машина Тьюринга, способная выполнять любые вычисления, тем самым дав утвердительный ответ на первый вопрос.
