Можно, но оно зависит от конкретного способа "алгоритмического описания".
Например, для машины Тьюринга над двухсимвольным алфавитом - это известная проблема Busy Beaver:
http://mathworld.wolfram.com/BusyBeaver.htmlhttp://en.wikipedia.org/wiki/Busy_beaverA028444