Talk:Along and Across

This looks suspiciously like the minimisation operator in μ-recursive functions. I don't fully understand μ-recursive functions, but apparently they are Turing complete (maybe?). I'm not sure if that helps much. Plokmijnuhby (talk)

It's not quite the same. For one thing, the minimisation operator can't be stateful between the values that are checked (i.e. if all values up to 4 have been checked, it has to start checking again at 5, whereas an "across" program can retain state between "along" outputs). More importantly, though, the minimisation operator is very general, whereas this is something of an extreme special case: it only allows one minimisation in the program, at the outside. (That's enough for Turing-completeness given a sufficiently expressive inside, but then Along and Across is Turing-complete given a sufficiently expressive "along" program.) --ais523 19:11, 26 May 2018 (UTC)

A variant is possible. Instead of a sequence of bits, you could specify that the along program takes a natural number as input (it doesn't matter whether it starts at 0 or at 1), and the combined program produces a single natural number as output (if it halts). --Zzo38 (talk) 04:33, 27 May 2019 (UTC)