Turing complet
Un sistema és Turing complet quan és capaç de realitzar qualsevol càlcul computacional que pugui descriure’s amb una màquina de Turing, sempre que disposi de temps i memòria infinits.
En altres paraules, un llenguatge de programació, una màquina virtual o un model computacional és Turing complet si pot simular qualsevol altre sistema computacional. Això implica que, amb els recursos adequats, pot resoldre qualsevol problema que sigui resoluble mitjançant algoritmes.
Exemples: la majoria de llenguatges de programació moderns (Python, Java, C++) són Turing complets. També ho són alguns sistemes sorprenents, com Minecraft Redstone o Conway’s Game of Life.
Més informació: Viquipèdia (català) · Wikipedia (anglès)
Per què és important?
- Defineix el límit del que és possible computar.
- És un concepte clau en informàtica teòrica i ciències de la computació.
- Mostra per què sistemes aparentment simples poden tenir el mateix poder computacional que un ordinador universal.
