Google controls the AMP project and the AMP library. They can start rewriting all links in AMP containers to Google’s AMP cache and track you across the entire internet, even when you are 50 clicks away from google.com.
Really? Could you publish how you are inspecting an unknown program to determine if it exhibits a specific behavior? There are a lot of computer scientists interested in your solution to the halting problem.
Joking aside, we already know from the halting problem[1] that it you cannot determine if a program will execute the simplest behavior: halting. Inspecting a program for more complex behaviors is almost always undecidable[2].
In this particular situation where Google is serving an unknown Javascript program, a look at the company's history and business model suggests that the probability they are using that Javascript to track use behavior is very high.
def divisors(n):
for d in range(1, n):
if n % d == 0:
yield d
n = 1
while True:
if n == sum(divisors(n)):
break
n += 2
print(n)
Also, if I execute a program and it does exhibit that behaviour, that’s a proof right there.
The same kind of analysis can be applied to Google’s scripts: look what data it collects and where it pushes data to the outside world. If there are any undecidable problems along the way, then Google has no plausible deniability that some nefarious behaviour is possible. Now, whether that is a practical thing to do is another matter; but the halting problem is just a distraction.
This has nothing to do with the halting problem because that is concerned about for all possible programs not some programs.
We obviously know if some programs halt.
while true: nop
X = 1
Y = X + 2
More complex behaviours can be easier. Neither of my programs there make network calls.
Likewise, AMP pages are mostly accessed from Google search that's already tracked.