4 ms·

Nice, but I'm not sure I get it. There is no such thing as a concrete non-deterministic operation. How does the expression evaluate? If all the parameters are e

by yuvadam 16y ago

Nice, but I'm not sure I get it. There is no such thing as a concrete non-deterministic operation. How does the expression evaluate? If all the parameters are evaluated in order, there's nothing non-deterministic about it.

yogsototh 16y ago
There is no known real world non-deterministic Turing Machine. We could only simulate it using a deterministic Turing Machine (like a common computer). Using this operator make the code really clear (IMHO) and I suppose it is its purpose. Furthermore, if one day we discover an hardware able to be a non-deterministic Turing machine is discovered, the code will work. [1]: I doubt such an hardware exists. But you could look about quantum computer for something close to what is a non-deterministic Turing machine.
- szany 16y ago
  Navia Systems is designing nondeterministic hardware. http://www.naviasystems.com/ http://www.naviasystems.com/
  - kd0amg 16y ago
    Maybe I'm missing something, but their web site appears to discuss probabilistic procedures, which is not nondeterminism in the Turing machine sense.
    - szany 16y ago
      No you're right. I missed the "preferring those choices that cause the program to converge meaningfully" part. Sorry. Disregard.
calibraxis 16y ago
"Non-deterministic" is a somewhat technical term... Wikipedia gives a good explanation of what aspect of this operation makes it be called nondeterministic. (http://en.wikipedia.org/wiki/Nondeterministic_algorithm http://en.wikipedia.org/wiki/Nondeterministic_algorithm)
stiff 16y ago
It is non-deterministic in the sense that the program itself and its inputs are not sufficient to determine the program behavior, as the amb operator creates a set of "possible worlds" in which the same expression has different values. Of course to implement it on a traditional computer, one has to simulate this behavior and decide on some order of evaluation. In SICP, where this is discussed in more depth, one of the exercises asks the reader to modify amb to return a random choice instead of just the subsequent one and this expands the range of problems one can apply this technique to: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_thm_4.49 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html... http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_thm_4.50 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html...

by yuvadam 16y ago

yogsototh 16y ago

There is no known real world non-deterministic Turing Machine. We could only simulate it using a deterministic Turing Machine (like a common computer). Using this operator make the code really clear (IMHO) and I suppose it is its purpose. Furthermore, if one day we discover an hardware able to be a non-deterministic Turing machine is discovered, the code will work. [1]: I doubt such an hardware exists. But you could look about quantum computer for something close to what is a non-deterministic Turing machine.

szany 16y ago
Navia Systems is designing nondeterministic hardware. http://www.naviasystems.com/ http://www.naviasystems.com/
- kd0amg 16y ago
  Maybe I'm missing something, but their web site appears to discuss probabilistic procedures, which is not nondeterminism in the Turing machine sense.
  - szany 16y ago
    No you're right. I missed the "preferring those choices that cause the program to converge meaningfully" part. Sorry. Disregard.

calibraxis 16y ago

"Non-deterministic" is a somewhat technical term... Wikipedia gives a good explanation of what aspect of this operation makes it be called nondeterministic. (http://en.wikipedia.org/wiki/Nondeterministic_algorithm http://en.wikipedia.org/wiki/Nondeterministic_algorithm)

stiff 16y ago

It is non-deterministic in the sense that the program itself and its inputs are not sufficient to determine the program behavior, as the amb operator creates a set of "possible worlds" in which the same expression has different values. Of course to implement it on a traditional computer, one has to simulate this behavior and decide on some order of evaluation. In SICP, where this is discussed in more depth, one of the exercises asks the reader to modify amb to return a random choice instead of just the subsequent one and this expands the range of problems one can apply this technique to: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_thm_4.49 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html... http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_thm_4.50 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html...