Для решения задачи начнем с числа 9 и будем последовательно применять команды, указанные в программе 12312:

Первая команда $1$: Приписать слева число $x$. Преобразуем 9:
$$9\to 10+x(\text{где}10\text{– это 9, приписанное к числу}x)$$

Вторая команда $2$: Вычесть 4:
$$(10+x)-4=6+x$$

Третья команда $3$: Разделить на 5:
$$\frac{6+x}{5}$$

Теперь повторяем команды с результатом.

Первая команда $1$: Приписать слева число $x$:
$$\frac{6+x}{5}\to 10+\frac{6+x}{5}$$

Вторая команда $2$: Вычесть 4:
$$\left(10+\frac{6+x}{5}\right)-4=6+\frac{6+x}{5}$$

Третья команда $3$: Разделить на 5:
$$\frac{6+\frac{6+x}{5}}{5}$$ Раскроем скобки:
$$=\frac{30+6+x}{25}=\frac{36+x}{25}$$

Теперь мы знаем, что после применения программы 12312 число должно получить значение 21:
$$\frac{36+x}{25}=21$$

Теперь решим это уравнение. Умножим обе стороны на 25:
$$36+x=525$$

Теперь решим для $x$:
$$x=525-36=489$$

Таким образом, искомое натуральное число $x$ равно $\boxed{489}$.