What I’ll tell you is limited to what we were taught in our course. So it might be incomplete. Turing actually defined what a “computation problem” is. He essentially made a theoretical machine that completely represents a human’s intuitive idea of a computation. So any problem which a human can solve, can be solved using a Turing Machine.
It essentially related a intuitive concept (like, what can we compute, or what can we not compute) to a well defined mathematical concept (a Turing Machine) and this is called the Church-Turing Thesis. (from what I know, Church had something to do with lambda calculus, which was proven to be what Turing said, but that was not taught to us)
Latest Answers