One of the things Turing is famous for is proving that the Halting Problem (whether or not a non-trivial program will ever terminate) is formally undecidable. Given any program where it isn't immediately obvious that it terminates (e.g. a string of commands with no branches) or does not terminate (e.g. a server program that basically waits in a loop for something to happen), Turing showed that there is no easier way to find out whether or not it terminates than to run it. And, of course, the fact that it hasn't terminated yet does not mean that it will not terminate - so "formally undecidable in most interesting cases", which is where the GP came in.
Boy, do I see a lawsuit brewing here. How can they legally justify paying straight people less than gays, if all other factors are equal? I don't care about any tax issues.
Easy: all other factors are not equal - ignoring tax does not make it go away (I share your dream, however). Effectively, you are arguing that it is legal for Google to choose equal gross pay, but not for them to choose equal net pay.
Does Google pay an apartment dweller more just because they don't get a mortgage write-off? Do they pay a single person more because he can't claim to be a head-of-household under IRS rules like a married person does?
These are choices that people make (often for reasons of failure of foresight, I'll admit), but they choose to put themselves in circumstances that lead to them paying more tax. Is gay a lifestyle choice? Remember that to win a lawsuit on these grounds, you'll have to prove in court that the answer is "yes" and, so far as I am aware, the evidence is not strong in either direction.
Do they pay a blind person less because they get two personal exemptions rather than one on their ISR 1040?
This one is not a lifestyle choice, but is easily defensible on grounds of additional costs experienced by disabled people in general. (such as a guide dog, equipment modifications and extra peripherals). Being gay or straight doesn't necessarily cost more, given the existence of adoption agencies.
...In short, it's not for Google to start correcting the unfairness of the tax system...
I think you hit a different nail from the one you were aiming at, but you're right on it's head. The tax system is unfair. Google's decision to correct for it doesn't favour gays or straights in terms of take-home pay, and this is all they need for defence because anti-discrimination laws all have exceptions for "genuine operational reasons" (for example, police attempting to infiltrate a white supremacist group can legally reject a black applicant based only on the colour of his skin). Google wishes to equalise take-home pay across protected characteristics (such as sexual orientation) while acknowledging extra costs faced by some groups (such as the disabled - which is independent of sexual orientation). That sounds like a genuine operational reason to me. The only argument I can see against it requires you to say that "...wishes to equalise gross pay..." is legal while "..wishes to equalise net pay..." is not - which is quite a difficult argument.
I could be wrong,
 Unless you put your own eyes out - but allow me this one assumption.
 The only non-homophobic argument, I should say, but the way you use "unfairness" and "correct" in your last sentence suggests to me that that's not your driver.