But not a single lookup table. If you can chain lookup tables it's equivalent to any other kind of gate. If you have to process all possible input combinations at once you can't do any meaningful computation.

This is how the famous Connection Machine 2's “one-bit processors” were implemented and programmed too, and basically the connection fabric is roughly analogous.

Indeed one can dynamically any kind of rapidly-reconfiguring FPGA-array into a very peculiar and high-performance general parallel processor.

That's correct, typically FPGA logic looks something along the lines of a bunch of logic feeding into a latch the output of which feeds into yet another bunch of logic and so on, and all this synchronized by a clock. The individual lookup tables are quite small, but in the aggregate together with the latches they can perform quite complex functions.