Функция машинального рисования — это невычислимая функция, разработанная Лоуренсом Холломом.[1] Это функция с двумя аргументами, аналогичная функции занятого бобра.
Определение[]
Функция вращается вокруг определённого типа одномерного клеточного автомата, в котором состояние ячейки определяется её собственным состоянием и состоянием ячейки справа от неё в предыдущем поколении (первоначальное объяснение Холлома немного отличается, но эквивалентно этому). Функция doodle(c,n) затем была определена как самое длительное время, в течение которого автомат может работать без повторения состояния, если мы ограничены автоматами с c состояниями и начальным значением длины не более n (с подсчётом пустых ячеек между непустыми ячейками).
Свойства[]
Путём приведения машины Тьюринга к этому типу автоматизации было показано, что функция машинального рисования не поддаётся вычислению, и фактически она в конечном итоге доминирует над каждой вычислимой функцией.
Значения[]
Вот некоторые известные значения и границы для функции машинального рисования:
doodle(1,n) = 1
doodle(2,n) = n
doodle(3,2) ≥ 487. Холлом проверил все возможные настройки с помощью компьютерной программы, и все остальные либо выполнялись за меньшее количество шагов, либо не выполнялись за 10 000 шагов. Он считает, что 487 - это точное значение этой функции.
Дополнение от Выходника[]
Так как в функции есть два аргумента, то её возведение в степень проблематично. Выходник дополняет функцию так, чтобы это стало возможным.
И так далее...