a_shen

ну это зависит от того, разрешать ли программу на ленте, то есть писать ли на ленте только вход x, или ещё можно до него написать программу. Во втором случае, если длина программы не учитывается, то состояний будет сравнительно немного, бывают универсальные машины с небольшим числом состояний. Если же ничего больше писать нельзя, тогда это зависит от функции и от алгоритма, думаю, что состояний тогда понадобится довольно много, хотя тут тоже, конечно, возможны какие-то соревнования по упрощению и пр.