What Is Non-Deterministic Computation?

Definition

Non-deterministic computation means one current configuration may allow more than one valid next configuration.

Simple form:

current configuration -> possible next configuration 1
current configuration -> possible next configuration 2

The system is not moving without rules.

The rules still define which moves are valid.

Non-deterministic computation = multiple valid next steps may exist

---

Not Random

Non-deterministic does not mean random.

Random means a choice is made by chance.

Non-deterministic means the model allows multiple possible next steps.

Example:

Current state: x = 5

Allowed:
5 -> 6
5 -> 4

This says both moves are possible.

It does not say one is chosen by probability.

Non-determinism is about possible paths, not chance.

---

Still Rule-Based

Non-deterministic computation still has rules.

Example:

Rule 1: if x > 0, x -> x - 1
Rule 2: if x > 0, x -> x + 1

Current state:

x = 3

Both rules apply:

3 -> 2
3 -> 4

The next state is not arbitrary.

Only the states allowed by the rules are possible.

Non-deterministic does not mean unconstrained.

---

Branching Execution

In deterministic execution, the trace is a single path.

In non-deterministic execution, the trace may branch.

Example:

        5
       / \
      4   6
     /     \
    3       7

From one state, more than one path may continue.

So instead of one execution trace, we may need to think about a tree of possible traces.

Non-deterministic execution can form a branching structure.

---

Configuration Branching

The branching happens from a full configuration, not just from a value.

Example:

Tape: [1] [0] [1]
          ^
Control state: scanning

Read symbol:

0

Two rules may apply:

(scanning, 0) -> (write 1, move right, next state returning)
(scanning, 0) -> (write 0, move left, next state scanning)

The same current configuration allows two valid next configurations.

Non-determinism is defined at the level of possible configuration transitions.

---

Same Input, Multiple Possible Traces

With non-deterministic computation, the same input can lead to more than one possible trace.

Example:

Input: 2

Allowed rules:
if x > 0, x -> x - 1
if x > 0, x -> x + 1

Possible trace:

2 -> 1 -> 0 -> stop

Another possible trace:

2 -> 3 -> 4 -> 5 -> ...

Same input.

Same rules.

Different possible paths.

Non-deterministic computation describes a set of possible traces.

---

Possible Does Not Mean Actual

When we list possible next configurations, we are describing what the rules permit.

Example:

current configuration -> move left
current configuration -> move right

This does not mean both movements happen as one physical action.

It means both are valid continuations in the model.

Non-determinism describes possible continuations, not simultaneous physical motion.

---

Why Use Non-Deterministic Models?

Non-deterministic computation is useful when we want to describe possibility.

It lets us ask:

• what paths are allowed?
• does at least one path reach a desired result?
• do all paths avoid an invalid result?
• where can execution branch?

This is useful even before thinking about implementation.

It gives a clean way to reason about possible behavior.

Non-determinism is a tool for analyzing possible computational paths.

---

Non-Deterministic Does Not Mean Confused

A non-deterministic system can be precisely defined.

Example:

From x = 5, allowed next states are {4, 6}.

This is clear.

What is not specified is which path is selected as the actual continuation.

The possible continuations are still exact.

Non-determinism can be precise even when the next path is not unique.

---

Deterministic As A Special Case

Deterministic computation is the case where each configuration has at most one next configuration.

Non-deterministic computation allows more than one.

Comparison:

Deterministic:
current configuration -> one next configuration

Non-deterministic:
current configuration -> possible next configuration 1
current configuration -> possible next configuration 2

The difference is the number of valid next steps.

The key distinction is uniqueness of the next configuration.

---

Final Summary

• Non-deterministic computation allows multiple valid next configurations.
• It is not the same as randomness.
• It is still rule-based and constrained.
• The same input may produce multiple possible traces.
• Branching happens from full configurations.
• Possible paths are allowed continuations, not necessarily simultaneous physical actions.
• Non-determinism is useful for reasoning about possible computational behavior.
• Determinism is the special case where each configuration has at most one next configuration.