Do identical algorithm end up having the same abstract syntax tree?

Question

More often than not, most programming problem can be solved in more than 1 way. You see this in website for practicing solving coding challenges where you often have myriad of solutions to the same problem.

My question is, do all these myriad solution all turn to the same AST in the language used? For example if I have 5 solutions in python to a problem, would these 5 solutions end up getting transformed to the same syntax tree?

I guess the crux of my question is, is there a way to "mechanically" identify that two algorithm are the same?

Answer 1

No.

In fact, it can be proven that you do not have an algorithm deciding whether two turing machines compute the same thing.

If you think about it a bit, you will see how being able to check if two TMs compute the same thing can solve the halting problem: If you are given a machine $M$ and an input $w$ to it, and want to check if $M$ will halt when it is fed with $w$, then construct the new machine $M_w$, that will have the following pseudocode:

1. Ignore the input $x$ to the machine $M_w$
2. Emulate $M$ on $w$
3. Return "true" for the input $x$ (that we totally ignored here), if the emulation stopped

This machine, will always return "true" if $M$ halts on $w$, but will never return "true" if $M$ doesn't halt. Now, we can easily construct another machine $M_{true}$ that always returns true, and since we assumed we can compare two machines to see if they compute the same things, then we can compare $M_w$ with $M_{true}$. As we have seen, if $M_w$ does indeed always return "true", then we know that $M$ halted on $w$, and if it doesn't always return "true" then we know that $M$ didn't halt on $w$.

In this way, we can see how knowing that two algorithms are the same can result us in solving an unsolvable problem. Hence, there is no "mechanical" way to check if two algorithms compute the same thing