Задача заключается в том, чтобы построить МТ, которая осуществляет переход 0q11^x01^y[$8594$]0q01ⁿ, где n= x^2 +3y
машина Тюринга MT = (Q,T,f,q0,q*), где
Q - множество внутренних состояний;
T - конечномерный алфавит символов строки;
f - функция переходов вида qa-> pbR, qa->pbL, qa->pb, где q,p Є Q, a,b Є T;
q1 Є Q - начальное состояние;
q0 Є Q - конечное состояние;

МТ физически состоит из ленты и головки. Головка может двигаться влево(L) или вправо(R) при этом записывать 0 или 1.

Работает МТ следующим образом:
qa-> pbR - МТ находится в состоянии qa. Головка читает символ а, переходит в состояние p и вместо а записывает b, при этом смещается вправо на одну позицию.
Я сначала построю МТ, вычисляющую x^2, на ее основе уже можно будет построить и требуемую функцию.
Идея такая - n^2=1+3+(2n-1)
Машина проходя стирает одну 1 в последовательности 1^x, и записывает 2x-1 единиц после. Потом она возвращается, и повторяет все сначала.

Чуток подправил: пропустили единичку в 0q11^x01^y[$8594$]0q01ⁿ

Алфавит какой {0,1}?