Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
object Injection {
// A table of constant 0 functions
def zeroes: Int => (Int => Int) = (n1: Int) => (n2: Int) => 0
// Update an entry in a function table with a new function at the given position.
def update(t: Int => (Int => Int), k: Int, f: Int => Int): Int => (Int => Int) = {
(n: Int) => if (n == k) f else t(n)
}
def diag(hinv: Int => (Int => Int)): Int => Int = {
(n: Int) => hinv(n)(n) + 1
}
def invert(H: (Int => Int) => Int): Int => (Int => Int) = {
@tailrec
def iter(hinv: Int => (Int => Int)): Int => (Int => Int) = {
val d = diag(hinv)
val k = H(d)
if (H(hinv(k)) == k) {
// Found a collision!
hinv
} else {
// The function at position k is incorrect, so update it and loop around.
iter(update(hinv, k, d))
}
}
iter(zeroes)
}
def solve(H: (Int => Int) => Int): (Int => Int, Int => Int, Int) = {
val hinv = invert(H)
val d = diag(hinv)
val k = H(d)
val fk = hinv(k)
(d, fk, k)
}
def solve2(H: (Int => Int) => Int): (Int => Int, Int => Int, Int) = {
// The constant 0 function
def g = (n: Int) => 0
// f(i) is zero everywhere except at i.
def f(i: Int) = (n: Int) => if (n == i) 1 else 0
@tailrec
def search(i: Int): Int = {
if (H(f(i)) == H(g)) i
else search(i+1)
}
val k = search(0)
(f(k), g, k)
}
}
object Examples {
def h1(f: Int => Int): Int = f(1) * 2
def h2(f: Int => Int): Int = f(1) + f(2)
def h3(f: Int => Int): Int = f(1) + f(f(0))
def h4(f: Int => Int): Int = f(1) + 5
def h5(f: Int => Int) = {
def pow(b: Int, e: Int) = math.pow(b, e).toInt
pow(2, f(f(0))) + pow(3, f(f(f(1)))) + pow(5, f(2)) + pow(7, f(3))
}
def h6(f: Int => Int) = {
def rec(f: Int => Int, x: Int, n: Int): Int = {
if (n == 0) x else f(rec(f, x, n-1))
}
rec((x: Int) => f(x) + 1, f(0), f(1))
}
def test(H: (Int => Int) => Int) = {
val (f, g, k) = solve(H)
println("H(f) = %d".format(H(f)))
println("H(g) = %d".format(H(g)))
println("f(k) = %d".format(f(k)))
println("g(k) = %d".format(g(k)))
(f, g, k)
}
def test2(H: (Int => Int) => Int) = {
val (f, g, k) = solve2(H)
println("H(f) = %d".format(H(f)))
println("H(g) = %d".format(H(g)))
println("f(k) = %d".format(f(k)))
println("g(k) = %d".format(g(k)))
(f, g, k)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment