HoTT without cuts (wild speculations)

Homotopical Type Theory in its current formulation has a way too huge proof theoretical ordinal strength for a metatheory. It would be practical to have a gradual control over its proof theoretical ordinal by means of adding or removing particular wellfoundness axioms. It seems, it can be easily done: first we have to remove all constructors for product types except linear lambda abstraction (so, no value duplication, no splits, no natrec). We will be able to emulate all this techniques with some help of interaction nets.

In HoTT we can define types with additional equality, for example the circle skeleton and the type of unordered pairs:

Family CircleSkeleton
  GenericPoint (CircleSkeleton)
  Loop (GenericPoint = GenericPoint)

Family Couple (Type ⇒ Type)
  Couple (T (Type), a (T), b (T) ⇒ Couple[T])
  Mirror (T (Type), a (T), b (T) ⇒ [Couple[T, a, b] = Couple[T, b, a]])

HoTT types form (∞,0)-categories, but we probably could allow nonreflexive arrows on the first H-Level to represent incomplete (or nonterminating) computations. Let's define a type of Natural numbers together with possibly incomplete addition:

Family Nat (Type)
  Zero (Nat)
  Succ (Nat ⇒ Nat)

Directed-Family Nat-Plus-Addition extending Nat
  Add (Nat, Nat ⇒ Nat-Plus-Addition)
  ZeroReduction (x (Nat) ⇒ [Add [Zero, x] = x])
  SuccReduction (a (Nat), b (Nat) ⇒ [Add[Succ[a], b] = Succ[Add[a, b]]])

Nat-Plus-Addition is now the type of expressions involving natural numbers and addition, and we can, step-by-step, by applying reductions, convert it to a Nat, preserving equality. ZeroReduction and SuccReduction are the computation rules in sense of Interaction Nets. Assuming univalence, ‖Nat-Plus-Addition‖ = Nat means precisely that Nat-Plus-Addition can always be reduced to Nat.

How can we prove that some ‖Type-Plus-Computation‖ = Type?
We certainly can do it only relatively to some wellfoundness postulate. Optimally, we have to represent ordinals α as universal interaction nets C_α of complexity up to α, than map interaction net Type-Plus-Computation in question onto C_α in such a way that elements of type Type are mapped onto Zero. The postulate that o is wellfounded should then have the form C_α = Unit we should be able to conclude that Type-Plus-Computation = Type.
Probably, we could use Takeuti Diagrams (encoded as Directed-Families) as universal interaction nets of corresponding complexities.

Прошлый пост

То, что прошлый пост написался 31 декабря – чистая случайность. Тем забавнее, что в нём я впервые смог сформулировать математическую мысль которая крутилась на самом деле весь год в голове:
– С тех пор как я поразбирался в HoTT я практически уверен, что это сила, кремень и будущее языков программирования и метаматематики.
– С тех пор как я начитался codedot'а я понял, что interaction nets рулят. Это реально элегантный, прозрачный, и оптимальный способ записывать пурые вычисления. Не то что машины Тьюринга, алгорифмы Маркова и лямбда-исчисление. Мне всегда казалось, что Fixpoint combinators и Church encoding это некрасивые dirty hacks, привносящие кучу нерелевантного произвола в модель вычислений, а теперь я убедился что это так.

Потом ещё под влиянием размышлений над макросами (спасибо xeno_by) я стал лиспером мне стало казаться, что тип данных AST должен быть в языках программирования явным и редукция выражений до представлений их значений тоже не должна быть под ковром. А в MLTT оно всё под ковром и очень лямбдёвое в плохом смысле. И вот с тех пор всё крутилось в голове, как бы так скрестить interaction nets и HoTT, да ещё чтобы выражения и их редукция были не под ковром. И вот потом щёлкнуло, что когда мы определяем новую функцию func, то это мы просто дополняем текущий тип AST ещё одним конструктором func, но при этом сразу определяем редукцию, при помощи которой этот конструктор может быть убран. Вот и получился прошлый пост.

На самом деле я уверен, что под тем или иным соусом это точно можно реализовать, и что соответствие Directed Inductive Types ~ Interaction Nets может оказаться весьма глубоким. Например, что такое равенства путей в сетях взаимодействия? — это формализация возможных оптимизаций. Возможно для чего-то может понадобится направленность и на этом уровне, ведь эти самые directed cubical sets как раз используются для того чтобы изучать Higher Automata (n-мерный автомат это просто автомат, у которого n лент ввода, на которые он реагирует независимо, не считая блокировок внутри, которые как раз и есть гомотопические свойства автомата).

Ну и отдельная тема, что HoTT неаскетичная теория, так что в идеале хотелось бы получить её точную истинную модель в рамках какой-нибудь совсем аскетичной теории, где ничего кроме натуральных чисел и диофантовых уравнений. ;-) См. http://akuklev.livejournal.com/1138512.html, естественно. Там всё, конечно, вообще вилами по воде писано, но больно уж красиво.