Revisiting this due to some related research I am doing, the disagreement between myself and some of the others who answered, can be assimilated into a holistic understanding in which we were all correct. But IMO the adopted computer science terminology “bounded nondeterminism” is an incorrect oxymoron (which was my point before).
They key point is to distinguish between bounded and unbounded nondeterminism.[1]
Nondeterministic Turing machines (aka “NTMs”) have bounded nondeterminism in that each state transition has a bounded number of possibilities, i.e. the number of programs (aka “configurations”) is finite. The tape remains unbounded, so the proof of termination remains undecidable. But for any given input that halts, the output is deterministic and bounded in time― i.e. for any input the result is deterministic or doesn’t terminate. Also NTMs execute all possible configurations in parallel, so they execute exponentially faster than emulation of NTMs on deterministic Turing machines (aka “DTMs”).[2]
There really isn’t any nondeterministic relationship between inputs and outcomes in NTMs because the outcome is always the same for any input or initial state, which is evident because they they can be emulated by DTMs without any added randomness.[2] Undecidable is not the antithesis of deterministic, because not halting is also a deterministic result. Deterministic machines always have the same outcome for a given input, even when that outcome is to not halt. The localized nondeterminism of NTMs is in each state transition of the executing algorithm. 915
It is undecidable a priori which path of the tree might terminate providing the output state. But undecidability is not nondeterminism. Thus the term “bounded nondeterminism” is intended to describe the localized indeterminacy within the state machine but not the relationship of inputs to results, hence the concept of “bounded”. I still think the term “bounded nondeterminism” is an oxymoron and it could have been more accurately described as a “parallelized state transition” <PERSON> machine.
Whereas, for any given input or initial state, unbounded nondeterminism (aka “indeterminism”) has an unbounded number of possible states. Unbounded nondeterminism involves not just the number of possible configurations of programs, but some unbounded external state which is not part of the input or initial state, such as unbounded delays. And thus outcomes can vary on repeated executions for the same input or initial condition; thus is not a deterministic relationship between inputs and outcomes.[3]
Randomized and probabilistic algorithms employ some nondeterminism, i.e. random selection of possible configurations possibly bounded in number of configurations, but they don’t execute all the possible configurations as NTMs do. Thus they are not deterministic unless the randomness is deterministic (e.g. PRNG) and the initial state of the entropy for the randomness is considered to be part of the input.
[1] https://en.wikipedia.org/w/index.php?title=Unbounded_nondeterminism&oldid=710628370#Nondeterministic_automata
[2] https://en.wikipedia.org/w/index.php?title=Non-deterministic_Turing_machine&oldid=754212081#Equivalence_with_DTMs
[3] <PERSON>, <PERSON> and <PERSON>: The Actor Model (everything you wanted to know...). Jump to the 17:44 minute mark. 915