not_nat_primrec_ack_self

Mathlib.Computability.Ackermann

URI: https://scilib.ai/kg/mathlib#not_nat_primrec_ack_self

← MathLib Explorer

English

The function n ↦ ack(n,n) is not a primitive recursive function.

Русский

Функция n ↦ ack(n,n) не является примитивно рекурсивной.

LaTeX

$$$$\\neg\\ Nat.Primrec\\ (\\lambda n.\\ ack(n,n)).$$$$

Lean4

theorem not_nat_primrec_ack_self : ¬Nat.Primrec fun n => ack n n := fun h =>
  by
  obtain ⟨m, hm⟩ := exists_lt_ack_of_nat_primrec h
  exact (hm m).false

Похожие утверждения

Научная платформа российской исследовательской школы.

Разделы

MathLib Explorer
Graph RAG
Лаборатория
Блог
О проекте
Команда

Аффилиация

Вычислительный центр им. А. А. Дороницына при ФИЦ «Информатика и Управление» РАН frccsc.ru