# Turing completeness: what a language can express

[Concepts explained](README.md)

A language or computational model is **Turing complete** if it can simulate any [Turing machine](alan-turing.md). This is about the computations it can express, assuming memory can grow without a fixed bound and there is no fixed time limit. It does not promise fast execution or unlimited hardware. See [Cornell's introduction to models of computation](https://www.cs.cornell.edu/courses/cs4820/2020sp/lectures/4820_computability.pdf).

## A small program to think about

This Pliro program remembers a value, checks a condition and repeats a step:

```pliro
# language: en
let remaining = 3
while remaining > 0:
    say remaining
    set remaining = remaining - 1
say "Ready!"
```

Predict the output before running it: three numbers, followed by a message. Change the starting value to five. Then try zero.

Variables, choices and repetition are useful building blocks for general programs. This example only demonstrates a countdown; it is not a proof of Turing completeness. Even a loop that never stops would not be enough evidence by itself.

## What it does not mean

**“It can solve every problem.”** Some questions have no algorithm that always gives the right answer for every input. The halting problem asks whether an arbitrary program will eventually stop on a given input. No algorithm always finishes and answers that question correctly for all programs and inputs in a universal model. See [Cornell's explanation of undecidability](https://www.cs.cornell.edu/courses/cs2112/2020fa/lectures/lecture.html?id=undecidability).

**“It can draw pictures or use the internet.”** Those require facilities supplied by the [runtime and host](runtime-and-host.md). A language's computational expressiveness does not grant access to a screen, file or network.

**“It passes the Turing test.”** That test concerns imitation of human conversation, a separate subject. Read [Alan Turing](alan-turing.md).

## How does this apply to Pliro?

Pliro supports variables, conditions, loops, functions and collections. You can combine them into increasingly ambitious programs. English and Dutch syntax describe the same underlying operations.

An actual Pliro session has finite memory and [runtime limits](../guides/limits.md), including instruction budgets and call-depth limits. A tight loop can be stopped with a diagnostic. These practical execution rules matter when running your code.

A formal claim about Pliro being Turing complete would need a precise model, explicit assumptions about resources and a proof that it can simulate a universal machine. A list of language features does not establish that claim, and this article does not present such a proof.

For your own project, start with concrete questions: can the program represent the information, make the decisions and use the host features it needs?

[Making loops stop](../guides/stopping-loops.md) · [Sandbox](sandbox.md) · [Compiler and interpreter](compiler-and-interpreter.md)