Чи може факторіал кодуватися в каппа-калькулі з оператором з фіксованою точкою?

Припустимо, що у нас є $ \ kappa $ -калькулюс з оператором $ fix $, який може бути використаний для перетворення функції з типом $ (1 \ rightarrow a) \ rightarrow a $ до значення типу $ 1 \ rightarrow a $. Ми використовуємо нормальну стратегію скорочення.

Ми хотіли б представити факторіальну функцію в такій системі. Проблема полягає в тому, що якою б функцією ми не намагалися знайти фіксовану точку, коли ми застосовуємо функцію до його точки виправлення, неможливо визначити, чи потрібно використовувати значення аргументу $ x $ чи ні. Там немає "лічильник", щоб база нашого рішення.

$ fix (\ kappa() x. \ cdots) = (\ kappa() x. \ cdots) (виправити (\ kappa() x. \ cdots)) $

У $ \ lambda $ -calculus ми можемо запустити $ fix (\ lambda f. \ Lambda x. \ Cdots) $ і закінчити в залежності від значення $ x $.

  1. Як довести, що $ \ kappa $ -calculus з оператором з фіксованою точкою не може реально представляти факторну функцію?
  2. Як ми могли б розширити $ \ kappa $ -calculus, щоб зробити його завершеним, залишаючи простір для його перекладу на узагальнені стрілки ?
5

1 Відповіді

Голий $ \ kappa $ -калькулюс не дозволяє визначити факторіал, навіть якщо його продовжити оператором з фіксованою точкою. Однак ця відповідь заслуговує деякого розпакування.

  1. The fixed point operator you give is not well-formed according to the grammar of types in the $\kappa$-calculus. Note that the grammar of types does not contain the function space $\tau \Rightarrow \tau'$ -- this is because the $\kappa$-calculus is a language of first-order functions. An expression has a type $\tau_1 \to \tau_2$, to indicate that it is an expression of type $\tau_2$, whose free variables are typed by $\tau_1$.

    The proper typing for a fixed point operator would be roughly something like: $$ \frac{\Gamma, x:1 \to \tau \vdash e : 1 \to \tau} {\Gamma \vdash \mu x:1 \to \tau. e : 1 \to \tau} $$

  2. Once you've fixed this, you still can't define a factorial.

    The plain $\kappa$-calculus does not have sums or natural numbers as a base type. As a result, you can't write branching programs, and so you cannot define interesting recursive functions. If you added natural numbers and their iterator, you could define a factorial function. Hasegawa actually gives factorial as an example in his paper on the $\kappa$-calculus, in a calculus augmented with a basic natural number type.

    However, you might wonder why you are able to define factorial in the pure lambda calculus, even though it has no apparent control structures. The reason is that the interaction of fixed points and recursion gives you a "universal type" (i.e., a type $V$ such that $V$ is isomorphic to $V \to V$), and this lets you encode any datatype as a subset (more accurately, a retract) of it.

    In more syntactic terms, you can write the Y combinator (i.e., Curry's paradox) in any language with (a) higher-order functions, (b) recursion, and (c) the ability to use each variable more than once in a program. Since the basic $\kappa$-calculus lacks (a), adding even an unrestricted fixed point operator does not make it Turing-complete!

9
додано
Забули, що узагальнені стрілки включають також примітиви для типу $ + $. Здається, мені потрібні свого роду первісні оператори рекурсії та мінімізації, щоб знову зробити $ \ kappa $ -calculus Тьюринг-повним. Дякую за чудову відповідь.
додано Автор William Martins, джерело