Church Turing thesis [closed]

What is the exact statement of the Church Turing thesis?

Is it fair to say anything computable in the physical world can be computed by a Turing machine? If so, how does a Turing machine handle continuous variable computations (for example, computing solutions to differential equations or storing/computing any real number)? It will take infinitely many tape squares to specify anything continuous. If the input itself is infinite, what does it even mean to compute based on the infinite input?

• In a nutshell, the Church-Turing thesis addresses pencil-and-paper methods. How do you represent real numbers on paper? Jun 21, 2019 at 7:35
• The Church–Turing thesis is not a formal statement. It doesn't have an exact statement. Jun 21, 2019 at 11:02
• Have you consulted Wikipedia? Jun 21, 2019 at 11:02
• Jul 18, 2019 at 9:17
• Possible duplicate of Is there any data structure that can't be represented or described inside a computer?. Although that question and answer does not mention Church-Turing thesis, it does address the vague questions raise here. Jul 20, 2019 at 2:31

1 Answer

Neither physical computers nor the Turing machine model can exactly represent the value of a continuous quantity or a non-rational transcendental real number. They can, for example, only approximate $$\pi$$ by calculating or storing its value to some finite (but maybe very large) number of decimal places.

You are right - any computation that requires an "infinitely long" input (e.g. "given an infinite list of integers, output the largest integer in the list") will take an infinite number of steps to finish (or even just to read its input), which is the same as saying it will never finish. But part of the definition of an algorithm is that it can be completed in a finite number of steps. So a computation on an infinite input cannot be expressed as an algorithm, and so it falls outside of the boundaries of the Church-Turing thesis.