Subj : Re: Incomputable
To   : comp.programming,comp.object
From : Dmitry A. Kazakov
Date : Thu Aug 18 2005 01:29 pm

On Wed, 17 Aug 2005 18:59:12 -0500, Chris Sonnack wrote:

> Dmitry A. Kazakov writes:
> 
>>>> Purely fictitious, let you can compute random distributions, rather
>>>> than their realizations (the only thing we can do now), then this
>>>> class of computing will be incomputable for any Turing machine.
>>> 
>>> Couldn't you do that now by using a true random (hardware) source?
>> 
>> Not really. The simplest thing: you cannot take a random generator
>> multiply it by another generator and get a third one - a product of.
>> You can multiply realizations, but that won't give you a new
>> independent generator.  The soul is gone... (:-))
> 
> Nice way to put it!
> 
> But can't you use two hardware sources?  (Maybe I just don't follow.)

Three, you mean. Yes I can, but that's not computing. It is hardware
construction. You can [possibly] assemble a generator, but you cannot
compute it. There is not enough computational states to identify all
possible random variables, even one particular variable. We enrich our
systems by attaching stateful elements.

> I mean the thing about Q/C is that it wants to use the hardware in a
> way that we work very hard to prevent it from working now!  I'm just
> not seeing the difference between a Q/M-driven source of random input
> (such as a semi-conductor junction) processed conventionally, and
> doing it all with Q/C.

The difference is huge. It would be not an input, but a value. It is the
difference between a function and its value in one particular point. In
terms of set theory it is a jump to a next cardinal number. [OK, it is all
fictitious, so far.]

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

.