15 Mar 2023

Turing Completeness

Turing machine is an endless piece of tape with 2 heads, one for reading, one for writing. It can compute anything that can be computed.

A language that is Turing complete when it is able to do anything a Turing machine can do.

Conditions

1. Has conditional branching (if statements)
2. Able to have an arbitrary amount of memory (as much as the problem needs).

Fun fact: CSS is Turing-complete.