Un automat celular este un model discret de computație folosit in studiul mașinilor abstracte, mai ales în știința abstractă a calculatoarelor. Acesta constă într-o matrice de celule, fiecare celulă fiind într-unul dintre stadiile posibile, de obicei 0 sau 1 (mort sau viu, stins sau aprins). Această matrice poate avea orice număr finit de dimensiuni. Pentru fiecare celulă definim o vecinătate relativă poziției sale. Se alege un stadiu aleator al celulelor    într-un anume timp t = 0 iar apoi se creează o nouă generație de celule în funcție de o anumită regulă predefinită, avansând timpul t cu 1. În mod obișnuit, regula unei noi generații este aceeași pentru fiecare celulă și nu se schimbă odată cu timpul, aplicându-se întregii matrici simultan.

     Clasificarea primară a unui automat celular, definită de către Stephen Wolfram, conține patru categorii:
  1. Automați care se stabilizează omogen (celulele rămân constante)
  2. Automați care ajung sa oscileze între anumite structuri stabile
  3. Automați care sunt complet imprevizibili, haotici

  4. Automați cu o structura foarte complexa, având structuri locale stabile și diferite. Această ultimă categorie este considerată universal capabilă să treacă de Testul Turing, devenind o Mașină Turing.