Two comments on the imposibility ...

["Shai Rubin" <shai@xxxxxxxxxxx>]

Two comments about issues that were discussed yesterday in the seminar


1. Prof. Reps noted that the Analysis algorithm used in the proof can
 be easily expressed by a Lambda expression: Lc.(Ly.c1y)(Lz.c0z) where L
 stand for Lambda  (I hope I got it right).  This Lambda expression takes
 one input (the variable c) and treats it as a combination machine. First,
 it reconstructs M   (Ly.c1y) and N  (Lz.c1z) (or, if you want one of their
equivalent
 representations) Then, it
 applies M on N.

 2. Prof. Horwitz question "what the property the Analysis algorithm
computes" is somewhat out of place. This does not mean that Prof. Horwitz
was wrong when asking the question. On the contrary, I was wrong  presenting
the proof in such a way that let this legitimate question  to arise. Talking
about a predicate in the proof was incorrect from the beginning (it was my
idea and not part of the paper).
The only thing the proof shows  is that there is something that I can
compute from the obfuscated program (the computation from 1 above), and the
oracle-access algorithm cannot; no need to mention a predicate at all.

Thanks for your time,

Shai