instIsPreorderPFunNatTuringReducible

Mathlib.Computability.TuringDegree

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

English

Turing reducibility is a preorder on the set of partial functions Nat → Nat.

Русский

Связь сводимости по Тьюрингу образует порядковое отношение на множестве частичных функций Nat → Nat.

LaTeX

$$IsPreorder (PFun Nat Nat) TuringReducible$$

Lean4

instance : IsPreorder (ℕ →. ℕ) TuringReducible where
  refl _ := .rfl
  trans := @TuringReducible.trans

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

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

Разделы

Аффилиация

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