# Implementing a Turing machine in Excel

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.