Comment by meatmanek | Hacker News Reader

Comment by meatmanek | Hacker News Reader

Parent Full thread

I think you're being overly (and incorrectly) pedantic about the meaning of "non-deterministic" -- you're applying the fairly niche definition of the term as used on finite automata, when the people you're refuting are using it in the sense of https://en.wikipedia.org/wiki/Nondeterministic_algorithm: "In computer science and computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm." I think this usage of the term is more common than the finite automata sense. Dictionary.com doesn't have non-deterministic, but its (relevant) definition of deterministic is "of or relating to a process or model in which the output is determined solely by the input and initial conditions, thereby always returning the same results": https://www.dictionary.com/browse/deterministic

Under that definition of (non-)deterministic, ironically, an NFA is deterministic, because it always produces the same result for the same input.

I'm not being pedantic, this is foundational comp-sci stuff drawing from the theory of computation (it's what the 'N' stands for in NP complete). That is not a particularly great (or relevant) wikipedia article you link to (you can look at the citations). The one on "Non-deterministic programming"[0] is probably better. But ultimately you can't just dismiss NFAs as these serve as the foundation for computational non-determinism. Automata theory isn't just some niche area of computing it's part of how we actually define what computation is.

We can just go straight to the Sipser (from the chapter 1, all emphasis is Sipser's)[1]:

> Nondeterminism is a useful concept that has had great impact on the theory of computation. So far in our discussion, every step of a computation follows in a unique way from the preceding step. When the machine is in a given state and reads the next input symbol, we know what the next state will be--it is determined. We call this deterministic computation. In a nondeterministic machine several choices may exist for the next state at any point.

> How does an NFA compute? Suppose that we are running an NFA on an input string and come to a state with multiple ways to proceed. For example, say that we are in state q_1 in NFA N_1 and that the next input symbol is a 1. After reading that symbol, the machine splits into multiple copies of itself and follows all the possibilities in parallel. Each copy of the machine proceeds and continues as before.

This is why the list monad also provides a useful way to explore non-determinism that mirrors in functional programming terms what NFAs do in a classical theory of computation framework.

To this point, LLMs can form this type of nondeterministic computing when they follow multiple paths at once doing beam search, but are unquestionably deterministic when doing greedy optimization, and still deterministic when using other single path sampling techniques and a known seed.

[0]. https://en.wikipedia.org/wiki/Nondeterministic_programming

[1]. https://cs.brown.edu/courses/csci1810/fall-2023/resources/ch...

You're just explaining what the word "nondeterministic" means when you put it before "finite automaton", which doesn't have much to do with what "nondeterministic" means in other places.

Nondeterminism before "finite automaton" is how the concept is developed in the theory of computation, which later develops into nondeterminism before "turning machine", and eventually before "polynomial time".

You seem to be misunderstanding the role automata theory plays in the larger framework of the theory of computation. It is not a "special case" of nondeterminism, it is the foundation for how all of the theory of computation is built.

Additionally, I'm also demonstrating how that exact same concept plays out in the other framework of computation, functional programming, and it works fundamentally the same way.

I have to say it's a bit surprising to need to defend the fundamental principles of computer science on HN. The topic is "how LLMs compute things" so using the computational definition of nondeterminism seem entirely relevant.

Reply on news.ycombinator.com