outcome is both cool and instructional
I’m going to have to go with “cry for help”.
I’m not even going to bother asking why; instead I’ll ask why the tape is always described as “infinite.” Isn’t it sufficient that it be very long? The only thing lost is the ability to run never-ending programs, which is impossible anyway.
It doesn’t help that I’m finally reading the Atrocity Archives. I saw the headline and asked myself when agents of the Laundry would show up.
It has to be infinite if you want to run arbitrary programs of unbounded size. Come on, tell me you’ve never wanted to run an arbitrary program of unbounded size.
basically it’s to avoid having to argue about space complexity, a practical detail which was theorized later. the point of the Turing machine was that one small set of rules about the actual logic (internal states of the machine) allowed the machine to compute everything which is computable. all that’s needed is a lot of input (i.e. the program and data), a lot of space for output, and a lot of scratch space.
since no one had actually developed a universal computer at the time, details about how much tape would be needed would have been rather ambitious. so, “infinite” covered the bases. “unbounded” is slightly more accurate, and slightly less discomforting.
added: the theoretical question at that time (which, notably, preceded the common understanding of “programs” as we know them, and was really a metamathematical question related to, a la gödel, whether every mathematical truth had a finite proof) was whether it was possible to predict whether programs would be “never-ending”. the answer, of course, is that it is not possible, but if the tape were finite, it would preclude asking the question.
I’ll give a 3rd explanation which I hope might be more clear. Suppose that you wrote a program trying to answer some yes or no question. You solve this problem by trying an infinite quantity of possibilities and seeing if they work or not. “Yes” means that there is at least one of these possibilities that works, “no” means that none of them do.
Then if the answer is yes, then the program will end in finite time / use a finite amount of tape. If the answer is no, then the program keeps running forever. How much time/tape is used? If you knew how much tape it will use (or if you had some finite upper bound) then you would have already found out that the answer is yes. i.e. You would have found some algorithm which is better than just trying everything. Unfortunately, there are some problems, such as the word problem in a finitely presented group, for which there is no algorithm better than just sitting down and trying everything one by one.
So you need infinite tape because you don’t already know the answer.
to add slightly to this, the “practical” version of this question is called static analysis, and is an active and interesting field. even though we can’t tell in advance whether we’ll need to brute-force or not, we might be able to at least learn something about real-world programs by looking at the source code without actually running them.
I understand - mostly - and yea, I’m more comfortable with “unbounded.” Can you tell my major was engineering, not math?
not really. there are plenty of math majors who know jack all about computational complexity theory, or in fact any subject that isn’t mandatory for the degree, and there are plenty of engineers who do. hell, there are quite a few engineers who know more math than a lot of math majors remember. fuck labels. seek truth.
“The intuitive mind is a sacred gift and the rational mind is a faithful servant. We have created a society that honors the servant and has forgotten the gift.” — Einstein
This topic was automatically closed after 5 days. New replies are no longer allowed.
