1) Get rid of the misfeatures that allow the problem to exist. Change the browser to never send headers that leak information by design (Referer, Cookie, Etag, User-Agent, etc).
1.1) (Optional) Fix stateful sessions that previously depended on cookies with a new HTTP session+authentication feature (that doesn't have the problems that made the Authorization header mostly useless).
2) Strip most of the other HTTP headers that leak bits of entropy so the browser fingerprint is too small (~16 bits max?) to be a unique id.
2.1) (Optional) Add some of the removed functionality back as a single header that reports a single "browser class" out of a handful (<32, 4-5 bits max. ~8 would be better) of predefined classes (e.g. "Standard Desktop with screen size between H1xW1 and H2xW2 with >=2 channel audio output. Supported codecs: audio=[MP3, AAC], video codec [...]", "mobile with multitouch screen with size ...etc...").
Of course, none of this will happen because the people with the power to make most of these changes derive a lot of their income from surveillance.
> Get rid of the misfeatures that allow the problem to exist. Change the browser to never send headers that leak information by design (Referer, Cookie, Etag, User-Agent, etc).
The internet is the problem. If you want to get rid of being tracked on the internet, you have to stop using the internet. If you remove user agents & cookies & tags, you don't solve the problem and you lose some useful features. None of those things keeps your ISP from watching, nor do they stop web sites from noting your IP & requests and storing them on their end. And for anything you have to log into, there's no point to hiding headers.
> Of course, none of this will happen because the people with the power to make most of these changes derive a lot of their income from surveillance.
That's probably not true now, and it's definitely not representative of the reasons the features we have were invented in the first place. Some people really did want custom features to identify a computer's capabilities. Without headers, we'd gimp caching, and we can't differentiate between mobile & desktop, for example.
I'm not sure why you're talking about the halting problem, that just isn't a serious concern in practice, it's a CS theoretic issue irrelevant to this thread or privacy. The major browsers will all let you kill stray JS processes.