Y Combinator, Partial Recursive functions

Posted on May 1, 2014
Tags: othermath

A total recursive function is an illusion.

A total recursive function simply a partial function that approximates the recursive function by nesting within itself an infinite number of times.

1 Partial recursive factorial

def fact0(n):
  if n == 0:
    return 1
  else:
    return "error"

def fact1(n):
  if n == 0:
    return 1
  else:
    return n* fact0(n-1)
def fact2(n):
  if n == 0:
    return 1
  else:
    return n* fact1(n-1)
def fact3(n):
  if n == 0:
    return 1
  else:
    return n * fact2(n-1)

2 A more general example

The partial recursive function takes itself as the parameter which it will use for the IH or recursive case.

partialrecursivefunction = lambda f: (lambda x: 1 if x == 0 else x * (f(x-1)))
sentinel = lambda x: "error"
p = partialrecursivefunction
s = sentinel
# error will display if the partial func isn't nested deeply enough

p(s)(1)
#> 'error'

p(s)(0)
#> 0

p(p(s))(1)
#> 1

p(p(s))(0)
#> 0

p(p(s))(2)
#> 'errorerror'

Observe that the input domain is limited by how nested the partial recursive function is.

3 Y-combinator

Y = lambda f: (lambda x: x(x))(lambda x: f(lambda *args: x(x)(*args)))
Y(p)(5)
#> 120

other examples of the y combinator

Y2 = lambda f: (lambda g: (g)(g))(lambda h: f (lambda x: (h)(h)(x)))
Y3 = lambda f: (lambda h: (lambda x: (f((h)(h)))(x) ) )(lambda h: (lambda x: (f((h)(h)))(x) ) )

Y2(p)(5)
#>120
Y3(p)(5)
#>120

non lambda version


def Y4(f):
  def app(g):
    return g(g)
  def hh(h):
    def xx(x):
      return (h(h))(x)
    return f(xx)

  return app(hh)
Y4(p)(5)
#> 120

4 A total recursive factorial

def fac(s,n):
  if n == 0:
    return 1
  else:
    return n* s(s,n-1)

fac(fac,5)
#> 120

5 Analogy

5.1 Taylor Series

  • as we add more higher level derivative terms to the series, the series becomes a closer approximate to the function.
  • as we add more partial functions, the resulting function becomes a closer awpproximate of the total recursive function.

5.2 Transitive relation

  • Let \(R\) be a relation from a set to itself,
  • Let’s compose the relation to itself 3 times
  • \(R \circ R \circ R\) would be the relations that are 3 levels deep, no more, NO LESS.
    • We can denote it \(R^3\)

\(R \cup R^2 \cup R^3\) would be analogous to our partial function p(p(p(s)))

\(\bigcup\limits_{n\in \mathbb{N}} R^{n}\) would be the total recursive function.