> On 13 Sep 2018, at 20:02, Philip Thrift <cloudver...@gmail.com> 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 <cloud...@gmail.com <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 everything-list+unsubscr...@googlegroups.com > <mailto:everything-list+unsubscr...@googlegroups.com>. > To post to this group, send email to everything-list@googlegroups.com > <mailto:everything-list@googlegroups.com>. > 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 everything-list+unsubscr...@googlegroups.com. To post to this group, send email to everything-list@googlegroups.com. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
