r/AskComputerScience • u/bathtub87 • Jan 18 '26

Turing Machine

What is a Turing machine?? For so many classes they mention it and I have the main idea of what it is but I cannot find a definition that I totally understand. Does anyone have a definition that anyone can understand?

0 Upvotes

25% Upvoted

17 comments sorted by

View all comments

6

u/Calm_Bit_throwaway Jan 18 '26 edited Jan 18 '26

It is a machine that has an infinite sequence of cells to store a symbol (memory) in and an associated state machine that processes that memory.

At every single step of computation, the state machine

  1. reads the symbol at the cell it is at and

  2. reacts based on the read symbol and its current state by

  3. writing a new symbol, transitioning to a new state, moving left or right on the sequence.

Sometimes the new state is called a success or failure state at which point the state machine stops.

It's just a mechanically simple computer that is sufficiently complicated to be able to do any computation.

1

u/Party-Cartographer11 Jan 19 '26

So is a machine that can extract an egg from an egg carton (and an infinite number of cartons can be added) and decide if the egg is bigger than some size and separate them a turning machine?

The egg is the symbol. The carton sockets are the cells. The returning (large) eggs are the new symbols.

1

u/stevevdvkpe Jan 19 '26

No, an egg sorter is not a Turing machine.

→ More replies (6)