BUT a pen and paper. A patent wouldn't be just the algorithm, but also a writing device and paper.
Everything is a theoretical until you do it in practice. You can't patent a cool 3D rendering algorithm. But you can patent a device that uses it and renders the output to a computer screen. This is how patents are written.
Well, yes, and if the patent says "a writing device and paper" it might be valid, because paper is a specific construct, and the patent obviously does not cover such things as e.g. a piece of cloth.
Why do you use bzip2 and not bzip? Well, because arithmetic coding is covered by a supposedly valid patent. However, bzip can be executed by hand, or on any multitude of devices satisfying the requirements for Turing-completeness. The idea that a patent should preclude the writing of bzip, a purely mathematical construct, is absurd. bzip runs on an abstract device.
You could, for instance, specify a specific processor in the patent, but this is not done. You could not, however, specify a processor architecture, because this is also a mathematical construct, which can be carried out on paper.
Let me give you an example: My uncle knows that a cell phone is a computer. How? Well, I told him, and I'm a researcher. How do I know? Well, originally, some professor told me, and he's a professor. How does he know? Well, he or his colleague studied the literature indicating that an ARM processor is Turing-complete... which, at the end of the day, is a totally mathematical consideration, independent of the physical world except perhaps the brains which analyze it.
>But you can patent a device that uses it and renders the output to a computer screen.
No, because each independent part of this is some prior art. The representation of data on silicon is long since public domain, the display of silicon data on a screen is long since public domain, the x86 architecture and the GPU architecture are mathematical, and the algorithm itself is mathematical, and the combination of these is not itself novel or interesting: it is not even performed except by the end user, who must merely double-click a game icon and shuffle some bits around with a mouse.
Actually I don't think its technically "Turing Complete". it doesn't have unbounded tape. In fact any given ARM processor will have a fixed addressable limit. I can certainly compute a class of things in theory that the ARM processor can't compute. There are real HW considerations that you need make when you deal with an actual physical processor that don't exist in the theoretical model.
And this sidesteps questions of complexity.
But this is similar to a patent on a new wing design. You can say it is simply a mathematical model of airflow and such. But the pudding is the creation, not the mathematical model of the wing.
Obviously -- it is a finite state machine, but this doesn't mean any less that it is a theoretical model.
>But this is similar to a patent on a new wing design. You can say it is simply a mathematical model of airflow and such. But the pudding is the creation, not the mathematical model of the wing.
No -- the wing is a physical object. I can hold a wing in my hand. Conversely, a patent on a wing design does not mean that I cannot use that wing design in a computer simulation of an airfoil. But a patent on bzip does mean, supposedly, that I cannot run bzip on a virtual machine. In other words, the wing design is the point, here: you could patent a specific device for running bzip, but you cannot patent bzip on all computing devices. Which, I suppose, might help to explain my point.