Stack Overflow
Stack Overflow

Questions tagged [non-deterministic]

Nondeterminism refers either to a computing system where the result may be one of many specified results or to a theoretical construct in which a computing system is allowed to try many options in parallel to search for a result.

Nondeterminism has several meanings in computing. In theoretical CS, nondeterministic computations are computations that have multiple options specified at various points and allows the computing machine to choose any of them. In programming, a nondeterministic computation is one where the result may vary from run to run due to factors such as thread timing or values from external devices.

238 questions
79
votes
12 answers

Does using heap memory (malloc/new) create a non-deterministic program?

I started developing software for real-time systems a few months ago in C for space applications, and also for microcontrollers with C++. There's a rule of thumb in such systems that one should never create heap objects (so no malloc/new), because…
The Quantum Physicist
  • 24,987
  • 19
  • 103
  • 189
55
votes
10 answers

How should I Test a Genetic Algorithm

I have made a quite few genetic algorithms; they work (they find a reasonable solution quickly). But I have now discovered TDD. Is there a way to write a genetic algorithm (which relies heavily on random numbers) in a TDD way? To pose the question…
James Brooks
  • 4,135
  • 4
  • 26
  • 25
48
votes
2 answers

Why is dictionary ordering non-deterministic?

I recently switched from Python 2.7 to Python 3.3, and it seems that while in Python 2 the ordering of dictionary keys was arbitrary but consistent, in Python 3 the ordering of the keys of a dictionary obtained with e.g. vars() appears…
Anaphory
  • 6,045
  • 4
  • 37
  • 68
47
votes
2 answers

Coercing floating-point to be deterministic in .NET?

I've been reading a lot about floating-point determinism in .NET, i.e. ensuring that the same code with the same inputs will give the same results across different machines. Since .NET lacks options like Java's fpstrict and MSVC's fp:strict, the…
Asik
  • 21,506
  • 6
  • 72
  • 131
42
votes
2 answers

Sql Server deterministic user-defined function

I have the following user-defined function: create function [dbo].[FullNameLastFirst] ( @IsPerson bit, @LastName nvarchar(100), @FirstName nvarchar(100) ) returns nvarchar(201) as begin declare @Result nvarchar(201) set @Result =…
opaera
  • 761
  • 2
  • 8
  • 8
34
votes
3 answers

What is the benefit of using exponential backoff?

When the code is waiting for some condition in which delay time is not deterministic, it looks like many people choose to use exponential backoff, i.e. wait N seconds, check if the condition satisfies; if not, wait for 2N seconds, check the…
xis
  • 24,330
  • 9
  • 43
  • 59
34
votes
4 answers

How can non-determinism be modeled with a List monad?

Can anyone explain (better with an example in plain English) what a list monad can do to model non-deterministic calculations? Namely what the problem is and what solution a list monad can offer.
Trident D'Gao
  • 18,973
  • 19
  • 95
  • 159
33
votes
1 answer

I do not understand the concept of Non Deterministic Turing Machine

I do not the understand the concept of Non Deterministic Turing Machine. I guess I understand the term Non deterministic algorithm : (nondeterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a…
Suhail Gupta
  • 22,386
  • 64
  • 200
  • 328
23
votes
4 answers

Erroneous for-loops in Java?

I observed erroneous behaviour running the following java-code: public class Prototype { public static void main(String[] args) { final int start = Integer.MAX_VALUE/2; final int end = Integer.MAX_VALUE; { long b = 0; for…
Sebastian
  • 281
  • 1
  • 8
23
votes
8 answers

Non-deterministic programming languages

I know in Prolog you can do something like someFunction(List) :- someOtherFunction(X, List) doSomethingWith(X) % and so on This will not iterate over every element in List; instead, it will branch off into different "machines" (by…
BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
22
votes
1 answer

Why is some code Deterministic in Python2 and Non-Deterministic in Python 3?

I'm trying to write a script to calculate all of the possible fuzzy string match matches to for a short string, or 'kmer', and the same code that works in Python 2.7.X gives me a non-deterministic answer with Python 3.3.X, and I can't figure out…
BioInfoBrett
  • 305
  • 1
  • 8
19
votes
2 answers

Why is concurrent haskell non deterministic while parallel haskell primitives (par and pseq) deterministic?

Don't quite understand determinism in the context of concurrency and parallelism in Haskell. Some examples would be helpful. Thanks
vis
  • 2,279
  • 1
  • 19
  • 27
18
votes
9 answers

Why does backtracking make an algorithm non-deterministic?

So I've had at least two professors mention that backtracking makes an algorithm non-deterministic without giving too much explanation into why that is. I think I understand how this happens, but I have trouble putting it into words. Could…
Jason Baker
  • 192,085
  • 135
  • 376
  • 510
17
votes
2 answers

Confusion about NP-hard and NP-Complete in Traveling Salesman problems

Traveling Salesman Optimization(TSP-OPT) is a NP-hard problem and Traveling Salesman Search(TSP) is NP-complete. However, TSP-OPT can be reduced to TSP since if TSP can be solved in polynomial time, then so can TSP-OPT(1). I thought for A to be…
Matt
  • 739
  • 2
  • 6
  • 10
16
votes
4 answers

Can precision of floating point numbers in Javascript be a source of non determinism?

Can the same mathematical operation return different results in different architectures or browsers ?
João Pinto Jerónimo
  • 9,586
  • 15
  • 62
  • 86
1
2 3
…
15 16