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