Turinggränsen

en tänkt gräns för vilka beräkningar som är möjliga med datorer. – Turinggränsen existerar som en konsekvens av antagandet att alla beräkningar som är intuitivt tänkbara kan utföras av en Turingmaskin (med andra ord: av en dator). Utanför Turinggränsen kan det alltså finnas beräkningar som inte kan utföras av en Turingmaskin, men som ändå är tänkbara. Med ”intuitivt tänkbara” beräkningar (till skillnad från teoretiskt tänkbara) menas beräkningar som en matematiskt kunnig person kan tänka ut och anse genomförbara. Att utföra de beräkningarna kan dock kräva hur mycket tid och resurser som helst. Beräkningarna måste vara digitala, eftersom Turingmaskiner är digitala. – Inom teoretisk datorvetenskap diskuteras ifall det går att överskrida Turinggränsen, alltså få en dator att utföra beräkningar som inte räknas som intuitivt tänkbara. Det krävs också att det bedöms vara möjligt att bygga en sådan dator. – På engelska: the Turing limit, även: the Church‑Turing limit.

[datorvetenskap] [ändrad 14 februari 2022]

Dagens ord: 2022-02-20