3 ms·
I don't think 'non-branching' is something we can rigorously define. I mean, lambda calculus doesn't have any build-in branching, but you can style write arbit
by eru 4y ago
I don't think 'non-branching' is something we can rigorously define.
I mean, lambda calculus doesn't have any build-in branching, but you can style write arbitrary programs in it. Same for 'post correspondence problem' or SKI calculus.
- pclmulqdq 4y agoI agree with you completely. People get hung up on the fact that the conjecture has a "2-way" decision, but if you redefine the problem, there are a ton of ways to make it have no decision points. The one I posed is a simple mutation, but there are turing machines that compute the Collatz algorithm, you can turn it into a geometry problem, etc. All of these can be defined as "branching" or "non-branching" however you want.
- eru 4y agoYes. 'Branching' and 'non-branching' make sense in the context of specific architectures and/or languages. Just not really in an abstract algorithmic sense.