Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
