Algorithms Or Interaction

From MistakesOfRogerPenrose

Has anyone had a look at the idea that, as computing is not purely algorithmic, RogerPenrose (and others) may be challenging a strawman. See PeterWegner's paper "The ParadigmShift from Algorithms to Interaction" (http://www.jeffsutherland.org/papers/wegacm.pdf) for a discussion on computing as an algorithmic process vs computing as a series of transactions.

One issue is whether the "series of transactions" takes the "formal machine" outside the capability of a UniversalTuringMachine. The ArtificialIntelligence community has made some strong statements about UTMs becoming "intelligent" in the TuringTest sense over the years and this has been taken pretty seriously, partly because of AlanTuring's own statements on the subject right at the beginning. If this is all a strawman then it's been a pretty robust and active one.

But one part of me is inclined to agree that the original claims were so stupid as to hardly need the level of detailed rebuttal given by Penrose. The emperor indeed has no clothes, but there again it's good to hear someone say it. Penrose is in any case more interested in the way he believes physics needs to develop to explain quantum gravity and the possible relationship between this and the working of the human mind. -- RichardDrake

Quote from the paper (pp2-3)

: Claim: Interaction-machine behavior is not reducible to Turing-machine behavior
: Informal evidence of richer behavior: Turing machines cannot handle the passage of time or interactive events that occur during the process of computation.
: Formal evidence of irreducibility: input streams of interaction machines are not expressible by finite tapes, since any finite representation can be dynamically extended by uncontrollable adversaries.
: The radical view that Turing machines are not the most powerful computing mechanisms has a distinguished pedigree. It was accepted by Turing, who showed in 1939 that Turing machines with oracles (like the oracle at Delphi that could predict the future) were more powerful than Turing machines. RobinMilner noticed as early as 1975 that concurrent processes cannot be expressed by sequential algorithms, while Manna and Pnueli showed that nonterminating reactive processes like operating systems cannot be modeled by algorithms. KurtGoedel's discovery that the integers cannot be completely described by logic, which demonstrates the limitations of formalism in mathematics, may be extended to show that interaction-machines also cannot be completely described by first-order logic.

Thanks for this quote. I'll reply with one from ShadowsOfTheMind (section 7.9, p381), which is the strongest statement in the book that Penrose says can be deduced from Goedel:

: Human mathematicians are not using a knowably sound alpha-order oracle machine in order to ascertain mathematical truth, for any computable ordinal alpha.
: The final conclusion of all this is rather alarming. For it suggests that we must seek a non-computable physical theory that reaches beyond every computable level of oracle machines (and perhaps beyond).

Does this help? Do interaction-machines take us out beyond any alpha-order oracle machine? -- RichardDrake

I will have to go off and read this in context, I assume that the stuff around it justifies the statement. (I take it an alpha-order oracle machine is a turing machine with oracle input?) -- ta

The alpha refers to how many times you apply Oracle recursively. I mean an oracle! To the basic UTM. I've added to the quote above to show that Penrose himself seems a bit alarmed at this point. The paragraphs leading up to this statement do indeed provide his justification. -- rd

You cannot predict the state of any system that has a random input stream, you cannot even do that for a deterministic input stream. The input might be a program to run ... think of the HaltingProblem.

At any given moment the history of interactions is finite. It could all be recorded onto one massive tape, and we can ask what a Turing machine would do with that tape. If that is the same as what a human would do if presented with the same history, we might reasonably say the human could be emulated by a Turing machine.

"any finite representation can be dynamically extended by uncontrollable adversaries." - I don't follow what this is trying to say. Is it like saying multiplying A*B is not a formal procedure because we can always come up with some new A and B? Sorry, but this sounds like nonsense to me. -- DaveHarris

There's a sense in which software may be considered non-algorithmic: it may contain bugs, and those bugs may actually be helpful to the users. For something to qualify as an algorithm, it has to have been deliberately designed to do a certain job and do it within certain boundaries. A "lucky hit" just happens at random, and will eventually go wrong at random, because what the noise giveth, the noise taketh away... -- DanielEarwicker. (PS. That is, if you ignore selection pressures!)

I really don't see where the problem is with interaction. Interaction between processes can easily be simulated by a TuringMachine: Take a description of the processes, their interconnection and their state as input and compute a successor state for each process. Repeat as often as desired. You want external input? Add it as an extra input for each iteration. This whole discussion is like saying storage and IO cannot be done by functional approaches. Haskell's monads are just one solution to this 'problem'. -- GunnarZarncke

CategoryMath CategoryPhilosophy