#1 By: Cory Doctorow, September 20th, 2013 17:22
#2 By: Gawain Lavers, September 20th, 2013 18:16
outcome is both cool and instructional
I'm going to have to go with "cry for help".
#3 By: Boundegar, September 20th, 2013 18:21
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.
#4 By: Tom Tjarks, September 20th, 2013 18:56
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.
#5 By: Allen McBride, September 20th, 2013 21:24
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.
#6 By: retchdog, September 20th, 2013 22:46
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.
#7 By: Adam Knapp, September 20th, 2013 23:23
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.
In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element. More precisely, if A is a finite set of generators for G then the word problem is the membership problem for the formal language of all words in A and a formal set of inverses that map to the identity under the natural map from the free monoid with inv...
So you need infinite tape because you don't already know the answer.
#8 By: retchdog, September 21st, 2013 00:10
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.
#9 By: Boundegar, September 22nd, 2013 00:05
I understand - mostly - and yea, I'm more comfortable with "unbounded." Can you tell my major was engineering, not math?
#10 By: retchdog, September 22nd, 2013 03:24
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
#11 By: Cory Doctorow, September 25th, 2013 17:22
This topic was automatically closed after 5 days. New replies are no longer allowed.