Алгоритмическая Проблема

конструктивный объект определенного вида (как правило, натуральное число или слово), содержащий в себе закодированную по фиксированным для алгоритмов данного типа правилам полную информацию об этом алгоритме. Обычно определение А. И. Формулируется таким образом, чтобы процедуры получения А. И. По исходному алгоритму и восстановления исходного алгоритма по А. И. Осуществлялись по возможности более просто. Изображение нормального алгорифма в алфавите А(не содержащем букв ) определяется как с..

описания - величина, характеризующая длину описания алгоритма. В зависимости от точной концепции алгоритма А. С. Описания уточняется по-разному. Единого достаточно устоявшегося уточнения к настоящему моменту (1977) не существует. Ниже рассмотрены наиболее часто встречающиеся случаи. Под сложностью описания нормально алгорифма обычно понимают длину его изображения, т. Е. Длину записи всех его формул подстановок в одну строку (между формулами проставляется специальная разделительная буква). По..

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

..