11–17 of 17 posts
This authors use of 'non-determinsistic' doesn't match the meaning of a Nondeterministic Turing machine used to define the complexity class NP.
There are many types of non-deterministic Turing machines, like a probabilistic Turing machine which flips a coin at each step.
But the 'maximally lucky guesser' or 'run all possibilities in one step' version of NTM's that defines NP is physically unrealizable.
> Magical computer that guess for you some data of course doesn't exists. Prolog does sunshine like this, no? You give it rules and then make a statement with a blank in it and it'll fill in the blank given the rules you've described.
Note of clarification. This authors use of 'non-determinsistic' doesn't match the meaning of a Nondeterministic Turing machine used to define the complexity class NP. There are many types of non-deterministic Turing machines, like a probabilistic Turing machine which flips a coin at each step. But the 'maximally lucky guesser' or 'run all possibilities in one step' version of NTM's that defines NP is physically unrea…
Also, surely NTMs are only physically unrealizable if P!=NP, and so whether or not NTMs could exist is an open question.
> Magical computer that guess for you some data of course doesn't exists. Prolog does sunshine like this, no? You give it rules and then make a statement with a blank in it and it'll fill in the blank given the rules you've described.
At a fundamental level Prolog works the same way that Python library works -- guessing and backtracking.
The idea seems so similar to the classical AMB ambiguous operator introduced by John McCarthy [0]. The implementation seems similar to what I've done a while ago, too, just in Lisp and using Lisp primitives rather than function decorators. [0] http://www.randomhacks.net/2005/10/11/amb-operator/ [1] https://github.com/phoe/amb/
The cool stuff here is the simplicity of the interface to it and its integration thanks to high order functional constructs (decorator).
Note of clarification. This authors use of 'non-determinsistic' doesn't match the meaning of a Nondeterministic Turing machine used to define the complexity class NP. There are many types of non-deterministic Turing machines, like a probabilistic Turing machine which flips a coin at each step. But the 'maximally lucky guesser' or 'run all possibilities in one step' version of NTM's that defines NP is physically unrea…
The code isn't magically solving NP vs P but it does simulate non deterministic run through a potentially exponential exploration.
Useful to explain non-determinism to students. I saw a similar idea before at https://github.com/aeporreca/nondeterminism which uses fork() to (inefficiently) explore all possible guesses concurrently
It doesn't help that CS students will potentially end up hearing the term "nondeterminism" to mean different things in different contexts. In the context of the linked repo, it's used in the way they'll probably encounter it when learning about Turing machines, but in less formal contexts it also gets used a lot to describe stuff like "Heisenbugs" where running something more than once doesn't necessarily end up in t…
In the context of a deterministic vs nondeterministic finite automata, a DFA has a linear computation path from the root to an accept/reject state and a NFA branches on epsilon transitions, continuing each potential computation (the "guesses") in so called "parallel universes" until one branch hits an accept state.
This definition follows with Introduction to the Theory of Computation 3rd edition by Sipser (would recommend)