CS Theory with Make

In this post, I play around with some make functions and eventually provide a constructive proof that the make syntax is turing complete via reduction to μ-recursion.

First, we have to construct numbers. I used the representation of numbers as unary strings of the character 0: ie, the number 4 is represented by 0000 (zero being the empty string). We can also compute the successor of a number:

# If this is called as a make function, $(1) will be replaced with the first
# function argument.
successor = O$(1)

$(info $(call successor,O))  # Outputs 'OO'

Life is a lot easier if we can compute predecesser. Luckily, this is pretty easy for us too:

monus_one = $(patsubst O%,%,$(1))

$(info $(call monus_one,OO))  # Outputs '0'

Now lets actually do computation with this. It is hideous, but we can actually compute fibonacci numbers in make:

fib = $(if $(1),$(if $(call monus_one,$(1)),$(call fib,$(call \
  monus_one,$(1)))$(call fib,$(call monus_one,$(call monus_one,$(1)))),O),O)

Let me try to break this up a bit. I'll add comments but it will no longer be valid make.

# fib (n):
fib = $(if $(1), # If n > 0:
          $(if $(call monus_one,$(1)), # if n - 1 > 0:
              # return fib(n-1) + fib(n-2)
              $(call fib,$(call monus_one,$(1)))$(call fib,$(call monus_one,$(call monus_one, $(1))))
          ,O) # else: return 1
      ,O) # else: return 1

This is pretty fun and all, but we haven't actually done anything that we couldn't do with a primitive recursive function. We can easily show that make is more powerful than primitive recusion by encoding the Ackerman function.

ack = $(if $(1),$(if $(2),$(call ack,$(call monus_one,$(1)),$(call \
  ack,$(1),$(call monus_one,$(2)))),$(call ack,$(call monus_one,$(1)),O)),$(2)O)

All right, so how far can we take this? As it turns out, there is a class of functions that are computable only by a turing complete language: µ-recursive functions. They are the primitive recursive functions with the addition of the minimization (µ) operator: µ of f(x) is the minimum x such that f(x)=0. As it turns out, we can encode this operator in make:

# muh f x returns the first number greater than or equal to x such
# that f(x) is true.
muh = $(if $(call $(1),$(2)),$(2),$(call muh,$(1),O$(2)))

# mu f returns the first number greater than or equal to 0 such
# that f(x) is true.
mu = $(call muh,$(1),)

Wow! There we have it, make is turing complete. As a final piece of fun, here is the inverse ackerman function:

not = $(if $(1),,O)

# lesseq_template n creates a function lesseq_y that returns y < x
define lesseq_template
  lesseq_$(1) = $$(findstring $$(1),$(1))
endef

# geack_template y creates a function geack_y that returns ack(x) > y
define geack_template
  geack_$(1) = $(eval $(call lesseq_template,$(1)))\
    $$(call not,$$(call lesseq_$(1),$$(call ack,$$(1),$$(1))))
endef

# invack n: Find the first value x such that ack(x) > n.
invack = $(eval $(call geack_template,$(1)))$(call mu,geack_$(1))

Comments !