1
$\begingroup$

In the Church-Turing thesis Wiki page, there are a set of descriptions of the "behavior of a computor—`a human computing agent who proceeds mechanically'". I am content with all of them, except:

(L.2) (Locality) A computor can shift attention from one symbolic configuration to another one, but the new observed configurations must be within a bounded distance of the immediately previously observed configuration.

I suppose this is related to the fact that in the standard description of a Turing machine, we are only allowed to move one step left or one step right at any step of the computation (e.g. the transition function is a map t : Symbols x States -> Symbols x States x {L,R}).

Indeed, this finiteness/locality assumption is present in Turing's original paper: in Section 9, Turing writes:

Besides these changes of symbols, the simple operations must include changes of distribution of observed squares. The new observed squares must be immediately recognisable by the computer. I think it is reasonable to suppose that they can only be squares whose distance from the closest of the immediately previously observed squares does not exceed a certain fixed amount. Let us say that each of the new observed squares is within L squares of an immediately previously observed square.

My issue with this is that I don't think it matches the standard motivating intuition provided for Turing machines (Turing himself provided this motivating picture in his original paper), namely that of some person, working with a finite set of symbols (e.g. all the symbols we can produce on a keyboard say), and finitely many "states of mind", reading/writing/erasing symbols on an unlimited pile of paper. I think it's entirely reasonable for that person, to flip an arbitrarily large number of pages forward or back in the pile/sequence of papers. Of course, if I wanted to flip a million pages back, I could! Or if I wanted to flip a trillion pages forward, I could!

Well, indeed in the standard model of Turing machines, I can have some sort of counter-variable holding the value of a million or trillion, and then take one step left or right, decrementing the counter-variable each time. So in this way, an unlimited number of steps left or right can be interpreted as just one step left or right, but over the course of many "units" of time.

But if truly unlimited numbers of steps left and right can be simulated by a standard Turing machine, why even bother stating this finiteness/locality "axiom"? I am having trouble understanding the subtlety of what sorts of "unlimited steps" left or right the "axiom" forbids, and what sorts of "unlimited steps" left or right the "axiom" allows (e.g. my "one trillion steps" example above).

EDIT: see also Intuition for Church-Turing thesis for Turing machines which says

The Church-Turing thesis says that any physically realizable computation does not require any "essentially nonlocal" operations.

I guess my above question is basically asking for a more precise understanding of what "locality" means. Fun bonus trivia: https://math.stackexchange.com/questions/402934/why-do-we-believe-the-church-turing-thesis mentions spacetime structures consistent with General Relativity which in some sense allow infinite computation in finite time!

$\endgroup$

2 Answers 2

2
$\begingroup$

A move of unlimited amplitude requires an unlimited amount of information for its description. There is no room in the model for such an amount, except on the tape. But it is not the purpose of the tape to encode move lengths explicitly.

$\endgroup$
1
$\begingroup$

While "unlimited" is also correct, "bounded" is much preferred.


Here is the expanded answer.

The new observed configurations must be within a bounded distance of the immediately previously observed configuration.

As you have explained, it is certainly reasonable and correct to replace "a bounded distance" with "a finite distance" (and replace "the immediately" with "a") in the quoted statement above. I prefer "finite" to "unlimited" since the latter might be interpreted as "possibly infinite", which is of course neither your intention nor the intention of any involved party.

However, I would like to stick to "a bounded distance", which means a distance that is bounded above from a fixed distance that only depends on the "computor". That limiting distance is the same for all successive changes of attention ever made by a specific computor.

Why?

Because one of the criteria to understand/define/create Turing machine is simplicity. According to Occam's razor, we should prefer explanations constructed with the smallest possible set of elements. Or according to Albert Einstein, "the supreme goal of all theory is to make the irreducible basic elements as simple and as few as possible".

It occurs to me that "a bounded distance" is simpler than "a finite distance" or "an unlimited distance". A distance that is "finite" or "unlimited" is somewhat harder to understand and explain because infinity is not easy to understand and explain. Infinity is a tricky beast (or, should I say, infinities are tricky?)

While "A computor" may shift attention to a new symbolic configuration that is "a finite distance" or "an unlimited distance" away from "a previously observed configuration", it might be the result of shifting attention many times. What we would like to describe/define/depict here is one atomic action of "a computor" that shifts attention from "the immediately previously observed configuration" instead of multiple actions. "Multiple actions" is understood as/defined by a sequence of successive atomic actions. The result of multiple actions is the aggregated consequence of all actions in the multiple actions. For example, I agree that "if I wanted to flip a million pages back, I could!". However, flipping a million pages back should be considered as flipping one page back a million times. Our interest here is about "flipping one page back" instead of "flipping one page back a million times".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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