Re:Church-Turing Thesis Cannot Possibly Be True [video]
by kaibee on Friday October 19, 2018 @10:44AM
(#18257037)
That seems to be the same thing as representing sqrt(2) as sqrt(2).
Re:Church-Turing Thesis Cannot Possibly Be True [video]
by mcguire on Friday October 19, 2018 @06:59PM
(#18260697)
Yes, sort of.
You can "compute" sqrt(2) by the geometric construction of a unit square and "drawing" the diagonal.
You cannot do it physically, because marks on paper are not geometric primitives: points are not 0-dimensional; when drawn with a pencil, they have a physical size. A line on paper is not 1-dimensional, etc. But on the other hand, all physical computers are actually equivalent to finite state machines: they don't have infinite (or, unbounded) storage.
I'm halfway through the video, and they are discussing this: the fundamental limit of Turing machines, etc., is that they cannot do an infinite (or unbounded) amount of work in a finite number of steps. As a result, geometric constructions a la Euclid are not computable.
I suspect that the proof is that geometry is uncomputable.