-2
$\begingroup$

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?

$\endgroup$

closed as unclear what you're asking by dkaeae, Evil, David Richerby, Apass.Jack, Discrete lizard Jul 21 at 16:00

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

1
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.