> You could argue that it doesn't really count though because it was only turing complete in theory

Then you have to also count the Z3 which predates the Colossus by 2 years.

[1] https://en.wikipedia.org/wiki/Z3_(computer)