--- Log opened Mon Aug 26 00:00:41 2013
01:46 < amiller> i started thinking about whether general/unbounded recursion can be implemented using snarks
01:47 < gmaxwell> amiller: I can imagine that code with the right "periodic" structure could be...
01:47 < gmaxwell> But it would be the same code that you could also prove its result in closed form.
01:47 < gmaxwell> And so, why not just put in the closed form code? :P
01:49 < amiller> well an example is like a list with unknown bound
01:49 < amiller> say a sum over such a list
01:50 < amiller> that would ordinarily require unbounded size input to the circuit which doesn't work
01:51 < amiller> but you can give it the root digest of a hash chain list and then that's obviously fine
01:52 < amiller> but still a circuit that just checks hashes would still have to check a bounded number of hashes
01:54 < gmaxwell> right sure, the challenge there is making something which is secure against a prover key generating oracle. otherwise, you would just rig the decisions to only check the right places.
01:55 < amiller> i think what i should do is show that iterations reaches a fixpoint somehow
02:21 < amiller> normally the possible configuration space of a turing machine is infinite
02:22 < amiller> because it can run for an unbounded amount of time and have add one more element to its unbounded tape at each step
--- Log closed Tue Aug 27 00:00:44 2013