Re:Church-Turing Thesis Cannot Possibly Be True [video]
by ghayes on Friday October 19, 2018 @02:18AM
(#18254555)
Doesn't computable numbers, from the reference Wikipedia article, only state they can be computed to a given nth digit? Thus, in the OP's example, the rule-and-compass construction is exact whereas the Turing machine could only approximate the number (unless given infinite time, which I assume is out).
[ Parent
| on HN ]
Re:Church-Turing Thesis Cannot Possibly Be True [video]
by alew1 on Friday October 19, 2018 @03:03AM
(#18254699)
We need a digital representation of real numbers. One possible choice is: a real number r is represented as the source code of a function which takes a natural number n to the nth digit of r. This seems no more like “cheating” (and to me, it is less like cheating) than to represent a real number r by a line segment of length r.
Re:Church-Turing Thesis Cannot Possibly Be True [video]
by dllthomas on Friday October 19, 2018 @01:15PM
(#18258217)
That can't represent most real numbers, although I don't know that we have actually established that physical lengths can.
Re:Church-Turing Thesis Cannot Possibly Be True [video]
by OscarCunningham on Friday October 19, 2018 @05:43AM
(#18255437)
Both representations have the feature that it's impossible to check whether two real numbers are equal.
Re:Church-Turing Thesis Cannot Possibly Be True [video]
by goldenkey on Friday October 19, 2018 @06:20AM
(#18255575)
Actually with the physical objects you could use one to occlude the other and test for light passage
Re:Church-Turing Thesis Cannot Possibly Be True [video]
by empath75 on Friday October 19, 2018 @06:54AM
(#18255722)
Not with infinite precision.
Re:Church-Turing Thesis Cannot Possibly Be True [video]
by aeneasmackenzie on Friday October 19, 2018 @11:17AM
(#18257262)
Importantly, this is actually true of the real numbers.
Re:Church-Turing Thesis Cannot Possibly Be True [video]
by OscarCunningham on Friday October 19, 2018 @01:42PM
(#18258466)
I don't think I believe in "actual" real numbers.
Re:Church-Turing Thesis Cannot Possibly Be True [video]
by iitalics on Friday October 19, 2018 @02:09PM
(#18258698)
The catch is that you can't actually measure the rule-and-compass construction with infinite precision. You can perform more operations on the construction and then measure later to verify that it produced the correct result, but so can a turing machine acting on a mere "representation" of the number.