Why is it that a Turing machine can perform all kinds of calculations and procedures? As a test, I tried to perform a four-quadratic calculation using a Turing machine myself. However, although I found that it can perform the four arithmetic operations as a result, I do not understand the principle of why it can do so. I do not know the principle of why it is possible. Even other procedures (like accounting software) should be able to be described by Turing machine, but I don't know the principle of why it is so. How can you say In principle, Turing machine can perform all kinds of calculations and procedures"? Can someone please help me out with this quandary?

  • 2
    $\begingroup$ Wikipedia might be relevant: en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis "Church, Kleene, and Turing proved that these three formally defined classes of computable functions coincide: a function is λ-computable if and only if it is Turing computable, and if and only if it is general recursive. This has led mathematicians and computer scientists to believe that the concept of computability is accurately characterized by these three equivalent processes." $\endgroup$ Apr 9, 2023 at 15:41
  • $\begingroup$ The rationale is the converse: until Turing, we had no precise notion of what a computation is. Turing proposed that a computation be what a Turing machine can do, which is based on a finite number of elementary operations on discrete data. A counter-example would be, say, the addition of two electrical currents by connecting two wires in parallel: this is not a computation. $\endgroup$
    – user16034
    Apr 10, 2023 at 18:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.