Cтраница 4
Рассмотрим применение этого алгоритма к входному слову caab. Входное слово содержит букву а два раза. [46]
Алфавитный оператор, не сопоставляющий данному входному слову а никакого выходного слова bj, не определен на этом слове. [47]
Если алфавитный оператор не сопоставляет данному входному слову р никакого выходного слова ( в том числе и пустого), то говорят, , что он не определен на этом слове. Совокупность всех слов, на которых алфавитный оператор определен, называется его областью определения. [48]
Алфавитный оператор, не сопоставляющий данному входному слову иг никакого выходного слова bj ( в том числе и пустого), не определен на этом слове. [49]
Если М начинает работу с входным словом w и допускает w, но вычисление дает два идентичных следа справа от входного слова, то существует допускающее вычисление машины М, начинающееся со слова w и использующее меньше времени и памяти. [50]
При работе алгоритма А над конкретным входным словом р, на котором этот алгоритм определен, исходная, промежуточная и конечная информации занимают лишь некоторую ограниченную ( конечную) часть информационной ленты, поскольку алгоритм работает лишь конечное число шагов и на каждом шаге записывает информацию не более чем в одну новую ячейку. Поэтому, если память машины М достаточно велика, можно поместить в выделенную выше ее третью часть требуемый участок информационной ленты. Затруднения же с возможной недостаточностью объема памяти, в силу принятого выше предположения, не должны приниматься во внимание при решении вопроса о-принципиальной представимости на машине тех или иных алгоритмов. [51]
Напишите подпрограмму, меняющую во входном слове младший и старший байты местами. Входной параметр является одновременно и выходным. [52]