20.50 Really Hard Problems
Are there problems that computers can't solve?
For some people this question is a no-brainer. For others, it's an interesting mathematical problem. For me, it's kind of both.
I'm not going to spoil the end of this story by telling you that mathematicians discuss this question when they talk about NP-Completeness, because, well, NP-Completeness has not yet been proven one way or the other. But there are more practical considerations, and, while I am not really qualified to explain NP-Completeness, I can explain the more practical problems with using computers.
I want to tackle each class of machine I have introduced, and outline the practical limits to their use, both relative to the current state of technology and to the theoretical limits on that class of machine.
Formulaic, or Formal Limits
We must not forget that all formulae are inherently limited in their interaction with the real world. A formula's function can be implemented in a real, physical machine, or it can be simulated. Simulation can be by hand calculation or by use of computers. Without such implementation or simulation, a formula simply can not by itself interact with the real world. That's a huge limitation.
Limits of Design and Construction
As I mentioned before, state-less machines tend to be mostly transformative in function. A wrench converts a loose nut to a tight nut. A lever converts a rock firmly planted on the ground to one which might more easily be shifted. A display converts a digital signal to a number or a color or a light level. A microphone converts a sound wave in the air to an electronic wave in a wire and a speaker converts an electronic wave in a wire to a sound wave in the air. An amplifier converts a weak signal to a strong signal. Etc.
State-less machines have various physical limits. A wrench doesn't work on a nut or a bolt of the wrong size, and if you use a cheap wrench on a nut or bolt that is too tight, you might break the wrench. Using a wrench as a hammer is often not very effective, and may also break the wrench. Rocks on levers can slip and levers can break. Rocks can crumble, too. Displays may not be designed to display the full range of numbers that can be input, or may not be designed to accept the full range that can be displayed. An amplifier can't put more power out than the power supply can give it, and the design of the amplifier will usually be a bit more restrictive than that because ideal amplifiers don't exist. Microphones, speakers, and amplifiers can be under-driven or over-driven, resulting in no sound or in noise. And sometimes the noise is interesting or useful in its own right. And so on.
These limits can be called limits of design and construction. All machines are subject to them, of course, not just stateless machines, but it's easier to point them out in stateless machines.
When machines are operated outside their limits, their operation is generally not well defined. They may work, or they may not, and it's often not really possible to determine beforehand. You just won't know until you've deliberately tried it a number of times and measured the results.
If it turns out that a particular machine is well-behaved outside its specified design limits, the machine is often re-specified to include the behavior that was not in the initial specifications.
General Limits of State-less Machines
In my earlier discussion of stateless machines, I pointed out that they cannot change their function based on previous input or output. That is, such changes in function are beyond the state-less nature of their design.
When a particular stateless machine turns out to have useful stateful functions, sometimes it is just re-specified.
But, since state-ful operations may interfere with state-less operations, state-ful operation may be considered erroneous. In that case, the machine would be redesigned to prevent the state-ful operation. If the state-ful operation is also desirable, the state-ful form of the machine may be sold as a different machine with a different set of specifications.