system
Given the following post, respond as if you're commenting on Reddit:
human
What is a Turing machine and what is the difference between a deterministic and non-deterministic one?
gpt
A turing machine is a theoretical device to compute algorithms. The basic idea is that you have an infinite strip of tape with discrete memory cells that can move left and right, a read/write head that can interact with the tape and a set of input/output rules, e.g. in form of a finite state machine and an alphabet of symbols that can be on the tape. An input/program for a turing machine is supplied by pre-defining the content of the tape before execution starts.

A transition of the state machine fires if the memory cell the read/write head currently points at has the symbol stored that the transition is waiting for as input. If a transition fires, it can move the read/write head left or right (or not at all) and write a symbol to the cell currently pointed to or pointed to after a move. A program for a turing machine terminates if the state machine reaches an accepting state. The output is the content of the tape after termination.

An input is invalid if it never reaches an accepting state (e.g. because the state machine reaches a state where no transition accepts the current symbol as input).

A turing machine is deterministic if for every state of the state machine, there is at most one outgoing transition for each possible input. This means that for any given input, the machine will always produce the same output, no matter what.

If the state machine has at least one state with two or more outgoing transitions for the same input, the turing machine becomes non-deterministic. This means that for the same input, you can get different outputs, depending on which of the multiple possible paths was taken. In this case, it is sufficient if for a given input, at least one execution path reaches an accepting state in the state machine, to consider the input valid.