В теории на удивление мало. теоретик вычислимости сказал бы, что все, что вам нужно, это mu-рекурсия или машина Тьюринга или тому подобное.
Однако, с практической точки зрения, вы не будете очень счастливы, пытаясь реализовать язык программирования на машине Тьюринга. Я бы сказал, что, как минимум, вы хотите иметь все обычные конструкции потока управления, примитивные типы данных, подпрограммы, а также массивы и структуры. Этого должно быть достаточно, чтобы вы могли реализовать это подмножество языка в самом языке - и затем вы можете начать с самого начала.