Пример 7.7
На ленте записано некоторое число, и головка обозревает одну из свободных секций (любую) левее записи. Составить программу прибавления единицы к этому числу. Программа:
Комментарий к работе программы подобен приведенному выше с той лишь разницей, что метка ставится перед исходным числом. Можно показать (это предлагается сделать в контрольных заданиях к данному разделу), что с помощью машины Поста реализуются (хотя и довольно громоздко) все арифметические действия над числами в унарной системе счисления*. Числа же, как было показано ранее, могут быть использованы для кодирования любой дискретной информации. В частности, состояние ленты можно представить словом в двоичном алфавите, где 0 будет соответствовать пустой секции, а 1 - отмеченной. В процессе работы меняется состояние ленты и, следовательно, от исходного слова происходит переход к выходному, представленному в том же двоичном алфавите. * Машина Поста обеспечивает весьма неплохую и полезную практику программирования. Недостатком оказывается чисто теоретический (т.е. непроверяемый) характер программ, однако он достаточно легко преодолевается, если построить эмуляцию машины на каком-либо языке программирования. |
|
Связь компьютеров по телефонным линиям Вернуться в оглавление: Теоретические основы информатики |
5937
5707