• The curious case of exponentiation in simply typed lambda calculus

  • 2024/05/04
  • 再生時間： 7 分
  • ポッドキャスト

The curious case of exponentiation in simply typed lambda calculus

無料で聴く

ポッドキャストの詳細を見る

  • サマリー

  • Like addition and multiplication on Church-encoded numbers, exponentiation can be assigned a type in simply typed lambda calculus (STLC). But surprisingly, the type is non-uniform. If we abbreviate (A -> A) -> A -> A as Nat_A, then exponentiation, which is defined as \ x . \ y . y x, can be assigned type Nat_A -> Nat_(A -> A) -> Nat_A. The second argument needs to have type at strictly higher order than the first argument. This has the fascinating consequence that we cannot define self-exponentiation, \ x . exp x x. That term would reduce to \ x . x x, which is provably not typable in STLC.

    続きを読む 一部表示

あらすじ・解説

Like addition and multiplication on Church-encoded numbers, exponentiation can be assigned a type in simply typed lambda calculus (STLC). But surprisingly, the type is non-uniform. If we abbreviate (A -> A) -> A -> A as Nat_A, then exponentiation, which is defined as \ x . \ y . y x, can be assigned type Nat_A -> Nat_(A -> A) -> Nat_A. The second argument needs to have type at strictly higher order than the first argument. This has the fascinating consequence that we cannot define self-exponentiation, \ x . exp x x. That term would reduce to \ x . x x, which is provably not typable in STLC.

続きを読む 一部表示

The curious case of exponentiation in simply typed lambda calculusに寄せられたリスナーの声

カスタマーレビュー：以下のタブを選択することで、他のサイトのレビューをご覧になれます。

Audible.co.jp

Amazon.co.jp
レビューはまだありません。