But they are programmable, very freely even. Whether you can start any desired program on the device is the crucial point. Having gates, doesn't influence what's inside the gates.

I'm reminded of Zed Shaw's argument about how python3 should not be considered Turing-complete if it can't run python2 code. It was a fun rhetorical exaggeration that I felt helped clarify that it isn't unable to run python2 code, but rather that the people in charge decided that it shouldn't.