In 1936, Alan Turing published “On Computable Numbers,” introducing what we now call the Turing machine: a minimal model able to simulate any effective algorithmic procedure.
With that model he proved the halting problem undecidable: no general algorithm can say whether an arbitrary program terminates. Church reached equivalent conclusions with the lambda calculus.
The Church–Turing thesis unified the notion of computability. Without that shared language, there would be no complexity theory and no clear basis for asking what a machine can “learn” or “reason.”
