> On 13 Sep 2018, at 20:02, Philip Thrift <[email protected]> wrote: > > > > On Thursday, September 13, 2018 at 9:18:15 AM UTC-5, Bruno Marchal wrote: > >> On 13 Sep 2018, at 14:21, Philip Thrift <[email protected] <javascript:>> >> wrote: >> >> >> >> Something I wrote some years ago (SKI related). In practice one would use a >> computer with a quantum-random number generator chip. >> https://spectrum.ieee.org/tech-talk/computing/hardware/a-chip-scale-source-for-quantum-random-number-generators >> >> <https://spectrum.ieee.org/tech-talk/computing/hardware/a-chip-scale-source-for-quantum-random-number-generators> >> >> >> https://poesophicalbits.blogspot.com/2013/06/skip-probabilistic-ski-combinator.html >> >> <https://poesophicalbits.blogspot.com/2013/06/skip-probabilistic-ski-combinator.html> >> : >> >> >> SKIP: Probabilistic SKI combinator calculus >> <https://poesophicalbits.blogspot.com/2013/06/skip-probabilistic-ski-combinator.html> >> >> Add to the S, K, and I combinators of the SKI combinator calculus >> <http://en.wikipedia.org/wiki/SKI_combinator_calculus> the P combinator: >> >> Sxyz = xz(yz) >> Kxy = x >> Ix = x >> P = K or KI with equal probability (0.5) >> >> It follows that Pxy evaluates to Kxy or KIxy, then to x or Iy = y with equal >> probability. > > > Interesting. It is, I guess, equivalent with the Turing machine + a random > oracle. Have you studied the quantum related idea, with P = 1/sqrt(2)(K + KI) > ? > > Bruno > > > > > I haven't looked at that. I just noticed a simple way to throw a "coin > tossing" combinator into the mix. SKI is apparently "Turing complete" [ > https://esolangs.org/wiki/S_and_K_Turing-completeness_proof ] so SKIP is in > principle enough to write Monte Carlo programs.
Yes, even just SK is Turing complete. This is what I am proving in the current “combinator thread”. Bruno > > - pt >> >> see also Evolutionary code and the probabilistic lambda calculus >> <http://poesophicalbits.blogspot.com/2013/05/evolutionary-code-and-probabilistic.html> >> >> and a SKI fixed-point combinator >> <http://en.wikipedia.org/wiki/Fixed-point_combinator#Other_fixed-point_combinators> >> >> >> >> - pt >> > > > -- > You received this message because you are subscribed to the Google Groups > "Everything List" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected] > <mailto:[email protected]>. > To post to this group, send email to [email protected] > <mailto:[email protected]>. > Visit this group at https://groups.google.com/group/everything-list > <https://groups.google.com/group/everything-list>. > For more options, visit https://groups.google.com/d/optout > <https://groups.google.com/d/optout>. -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
