Гугология Вики
Advertisement

Функция спокойного утконоса (англ. Placid platypus function), обозначаемая как , является "обратной" функции занятого бобра.[1][2] определяется как минимальное количество состояний, необходимое для МТ, которая печатает строку из единиц и останавливается. Впервые она была исследована и назван Джеймсом Харландом[3], в рамках его проекта исследования машин Тьюринга Безумный зоопарк[4].

Функция спокойного утконоса демонстрирует гораздо более сложное и непредсказуемое поведение, чем её обратная сторона. Во-первых, она немонотонна. Даже её вычислимость является нерешённой проблемой.

Примечания[]

  1. Джеймс Харланд (2016) Машины занятых бобров и наблюдательная эвристика выдры (или как приручить ужасных драконов) Theoretical Computer Science 646, 20: 61-85. (Препринт на arxiv)
  2. Джеймс Харланд. Занятой бобёр, спокойный утконос и другие сумасшедшие животные Двенадцатые вычисления: Австралазийская теория Симпозиум, Хобарт (2006) (Архивировано из оригинала 20 августа 2016)
  3. Джеймс Харланд в МКТУ, Австралия
  4. Джеймс Харланд. Занятой бобёр, спокойный утконос и другие сумасшедшие животные
Advertisement