Space, Mechanism and Interactability
By MortazaviBlog on Jul 31, 2005
The space used to encode a problem and the machine (mechanism) used for solving it cannot transform an interactable problem to a tractable one.
Instead, interactability may have its most important relationship to the logical form (or description) of the problem.
This hypothesis suggests itself when one examines the description of recursively enumerable sets and the computing levels in the arithmetical hierarcy. (See Chapter 4 of Robert I. Soare's Recursively Enumerable Sets and Degrees.)