> If anything, Makefiles are too powerful and too close to turing complete.

"Close to"? Not a formal proof of Turing-completeness (and may only work with GNU make, not sure), but...

  [me@host: ~]% cat fibo.mk
  dec = $(patsubst .%,%,$1)

  not = $(if $1,,.)

  lteq = $(if $1,$(if $(findstring $1,$2),.,),.)
  gteq = $(if $2,$(if $(findstring $2,$1),.,),.)
  eq = $(and $(call lteq,$1,$2),$(call gteq,$1,$2))
  lt = $(and $(call lteq,$1,$2),$(call not,$(call gteq,$1,$2)))

  add = $1$2
  sub = $(if $(call not,$2),$1,$(call sub,$(call dec,$1),$(call dec,$2)))

  fibo = $(if $(call lt,$1,..),$1,$(call add,$(call fibo,$(call dec,$1)),$(call fibo,$(call sub,$1,..))))

  numeral = $(words $(subst .,. ,$1))

  go = $(or $(info $(call numeral,$(call fibo,$1))),$(call go,.$1))

  _ := $(call go,)
  [me@host: ~]% make -f fibo.mk
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55
  89
  144
  233
  377
  610
  987
  1597
  ^C