Yes, exactly. Anywhere the name of a function appears, replace it with the expression defining the function. (Also, I’m ignoring higher-order functions, function pointers, and the like; presumably the problem is undecidable in languages with those kinds of features, since it’s basically just beta-equivalence of lambda terms. But we don’t need those features to get a Turing-complete language.)
No. To clarify, we’re not reducing any of the atomic operators of the language—e.g. we wouldn’t replace (0 == 0) ? 0 : 1 with 0. As written, that’s not a beta-reduction. If the ternary operator were defined as a function within the language itself, then we could beta-reduce it, but that wouldn’t give us “0”—it would give us some larger expression, containing “0 == 0“, “0”, and “1”.
Actually, thinking about it, here’s something which I think is equivalent to what I mean by “expand”, within the context of lambda calculus: beta-reduce, but never drop any parens. So e.g. 2 and (2) and ((2)) would not be equivalent. Whenever we beta-reduce, we put parens around any term which gets substituted in.
Intuitively, we’re talking about a notion of equivalence between programs which cares about how the computation is performed, not just the outputs.
Can you elaborate on what you mean by “expand”? Are you thinking of something analogous to beta-reduction in the lambda calculus?
Yes, exactly. Anywhere the name of a function appears, replace it with the expression defining the function. (Also, I’m ignoring higher-order functions, function pointers, and the like; presumably the problem is undecidable in languages with those kinds of features, since it’s basically just beta-equivalence of lambda terms. But we don’t need those features to get a Turing-complete language.)
Ok, I’m still confused.
Does
0
count as a expansion of:
f()
where
f() := (0 == 0) ? 0 : 1
?
No. To clarify, we’re not reducing any of the atomic operators of the language—e.g. we wouldn’t replace (0 == 0) ? 0 : 1 with 0. As written, that’s not a beta-reduction. If the ternary operator were defined as a function within the language itself, then we could beta-reduce it, but that wouldn’t give us “0”—it would give us some larger expression, containing “0 == 0“, “0”, and “1”.
Actually, thinking about it, here’s something which I think is equivalent to what I mean by “expand”, within the context of lambda calculus: beta-reduce, but never drop any parens. So e.g. 2 and (2) and ((2)) would not be equivalent. Whenever we beta-reduce, we put parens around any term which gets substituted in.
Intuitively, we’re talking about a notion of equivalence between programs which cares about how the computation is performed, not just the outputs.