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à)
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 tenen el mateix poder computacional que un ordinador universal.
Referències
- Scarfe, P., Watcham, K., Clarke, A., & Roesch, E. (2024). A real-world test of artificial intelligence infiltration of a university examinations system: A “Turing test” case study. PLoS One, 19(6) doi:https://doi.org/10.1371/journal.pone.0305354
- Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to automata theory, languages, and computation (3rd ed.). Pearson.
- Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2(42), 230–265.
- Viquipèdia. (s.d.). Turing complet. En Viquipèdia. Recuperat de https://ca.wikipedia.org/wiki/Turing_complet
- Wikipedia. (s.d.). Turing completeness. In Wikipedia. Retrieved from https://en.wikipedia.org/wiki/Turing_completeness