As far as I can tell, GLUTs have to fail Turing tests for relativistic reasons.
Presumably lookup tables need to be stored somewhere in the universe. The number of possible lookups a GLUT might have to do to respond to whatever’s happened in a Turing test so far grows exponentially with time, so the distance information has to travel from some part of the lookup table to an output device also grows exponentially with time (and Grover’s algorithm doesn’t change this). Since the information can’t travel faster than the speed of light, before long a tester would notice an exponential slowdown in the GLUT’s response times to questions...
Algorithms as dumb as GLUTs can’t sensibly respond to their environments in constant time even in principle.
As far as I can tell, GLUTs have to fail Turing tests for relativistic reasons.
Presumably lookup tables need to be stored somewhere in the universe. The number of possible lookups a GLUT might have to do to respond to whatever’s happened in a Turing test so far grows exponentially with time, so the distance information has to travel from some part of the lookup table to an output device also grows exponentially with time (and Grover’s algorithm doesn’t change this). Since the information can’t travel faster than the speed of light, before long a tester would notice an exponential slowdown in the GLUT’s response times to questions...
Algorithms as dumb as GLUTs can’t sensibly respond to their environments in constant time even in principle.