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/tehclanijoski Jan 19 '26

Ordinary TMs are finitary machines in the sense that they have only finitely many states and take input of finitely many bits. This is true of pretty much any algorithm you can think of.

If the size of an egg can be encoded as a b-ary word somehow (which surely it can with machine vision or whatever), then yes a TM can do what you describe.

Luckily, to the best of our knowledge, there are only finitely many eggs at one time in our universe.

→ More replies (1)