Машина Тьюринга и Алгоритм Евклида

[Николай]

Здравствуйте. Мне попалась книжка Б.А.Трахтенброт "Алгоритмы и машинное решение задач" Москва, 1957 (неужели в 57-ом в Советском Союзе были машины сложнее счётов? ). Там на странице 74 дано описание работы Машины Тьюринга, вычисляющей наибольший общий делитель двух чисел A и B.
Я решил на основе этого описания написать программу на Фортране (зачёт по ТА надо же получать ). Главная особенность программы в том, что управляющая головка (UG) действительно «ездит» по ленте (т.е. если она из ячейки 3 переместилась в ячейку 5, то она побывала и в ячейке 4 и обозрела её содержимое). Т.о., набор команд ограничивается тремя: Право, Лево, Стоп. Второй принципиальный вопрос – машина «принимает решение», что делать дальше, исходя только из содержимого обозреваемой ячейки. Я веду к тому, что писал настоящую машину Тьюринга, а не имитацию.

[Николай]

Теперь, собственно, код

      PROGRAM EVKLID
      !БЛОК ЗАДАНИЯ ПЕРЕМЕННЫХ!
      CHARACTER(1), ALLOCATABLE :: LENTA(:)
      INTEGER :: TAKT=0, UG, N, F, FIX
      CHARACTER(1) :: NULL='-', ONE='|',  A='A', B='B'
      CHARACTER(50) :: SLOVOA='A.TXT'
      CHARACTER(50) :: SLOVOB='B.TXT'
      !ЗАПИСЬ НА ЛЕНТУ СЛОВ A И B!
      ALLOCATE (LENTA(1000000))
      LENTA=NULL 
      I=5
      OPEN (1, FILE = SLOVOA, STATUS='OLD')
      DO WHILE (.NOT. EOF(1))
      read(1,*,iostat=ios) LENTA(I)
      I=I+1
      IF (IOS.NE.0) STOP 'ОШИБКА ПРИ СЧИТЫВАНИИ ФАЙЛА1'
      END DO
      CLOSE(1)
      OPEN (2, FILE = SLOVOB, STATUS='OLD')
      DO WHILE (.NOT. EOF(2))
      I=I+1
      read(2,*,iostat=ios) LENTA(I)
      IF (IOS.NE.0) STOP 'ОШИБКА ПРИ СЧИТЫВАНИИ ФАЙЛА2'
      END DO
      CLOSE(2)
      !ПЕЧАТЬ ИСХОДНОЙ ЗАПИСИ НА ЛЕНТЕ!
      OPEN(UNIT=4,FILE='RESULT.TXT',STATUS='UNKNOWN')
      WRITE(4,3)
    3 FORMAT(1X,'ИСХОДНАЯ ЗАПИСЬ НА ЛЕНТЕ')
      WRITE(4,*) (LENTA(J), J=1,I+5)
      !ПРИВЕДЕНИЕ ЛЕНТЫ В ИСХОДНОЕ ПОЛОЖЕНИЕ!
      !УПРАВЛЯЮЩАЯ ГОЛОВКА ОБОЗРЕВАЕТ ПЕРВУЮ ЯЧЕЙКУ!
      UG=5
      LENTA(UG)=NULL
      DO
      TAKT=TAKT+1
      UG=UG+1
      IF (LENTA(UG).EQ.NULL) THEN
        EXIT
      ELSE
        CYCLE  
      ENDIF
      ENDDO  
      LENTA(UG)=ONE
      WRITE(4,5)
    5 FORMAT(' ')
      WRITE(4,4)
    4 FORMAT(1X,'ПЕРВАЯ КОНФИГУРАЦИЯ = X+Y')
      WRITE(4,*) (LENTA(J), J=1,I+5)
      WRITE(4,5)
      !ИСХОДНОЕ ПОЛОЖЕНИЕ ДОСТИГНУТО!
      DO 100
      !ЗДЕСЬ УПРАВЛЯЮЩАЯ ГОЛОВКА БЕГАЕТ ТУДА-СЮДА!
      LENTA(UG)=A
      FIX=UG
      N=0
      F=1
      DO
      UG=UG+F
      TAKT=TAKT+1
      IF (LENTA(UG).EQ.ONE) THEN
        IF (F.EQ.1) THEN
            LENTA(UG)=B
        ENDIF
        IF (F.EQ.-1) THEN
            LENTA(UG)=A
        ENDIF
        N=N+1
        F=(-1)**N
      ENDIF
      IF (LENTA(UG).EQ.NULL) THEN
        UG=UG-F
        EXIT
      ELSE
        CYCLE
      ENDIF
      END DO
      WRITE(4,7)
    7 FORMAT(1X,'КОНФИГУРАЦИЯ ПОСЛЕ СРАВНЕНИЯ')
      WRITE(4,*) (LENTA(J), J=1,I+5)
      WRITE(4,5)
      !ЭТАП СРАВНЕНИЯ ЗАВЕРШЁН. НАЧИНАЕТСЯ ЭТАП ВЫЧИТАНИЯ!
      IF (LENTA(UG).EQ.A) THEN
      DO
      IF (LENTA(UG).EQ.NULL) EXIT
        IF (LENTA(UG).EQ.A) LENTA(UG)=NULL
        IF (LENTA(UG).EQ.B) LENTA(UG)=ONE
      UG=UG+1
      TAKT=TAKT+1
      IF (LENTA(UG).EQ.ONE) THEN
            UG=UG+F
            EXIT
        ELSE
            CYCLE
        ENDIF
      ENDDO
      ENDIF
      IF (LENTA(UG).EQ.B) THEN
        DO
        IF (LENTA(UG).EQ.NULL) EXIT
        IF (LENTA(UG).EQ.A) LENTA(UG)=ONE
        IF (LENTA(UG).EQ.B) LENTA(UG)=NULL
      UG=UG-1
      TAKT=TAKT+1
        IF (LENTA(UG).EQ.ONE) THEN
            UG=UG+F
            EXIT
        ELSE
            CYCLE
        ENDIF
        ENDDO
      ENDIF
      WRITE(4,5)
      WRITE(4,12)
   12 FORMAT(1X,'КОНФИГУРАЦИЯ ПОСЛЕ ВЫЧИТАНИЯ')
      WRITE(4,*) (LENTA(J), J=1,I+5)
      WRITE(4,5)
      IF (LENTA(UG).EQ.NULL) EXIT
      !ЭТАП ВЫЧИТАНИЯ ЗАВЕРШЁН!
  100 CONTINUE
      !ВСЁ. КОНЕЦ!
      PRINT *, UG
      PRINT *, (LENTA(J), J=1,I+5)
      WRITE(4,13)
   13 FORMAT(1X,'ЕСЛИ В ПОСЛЕДНЕЙ КОНФИГУРАЦИИ ПОСЛЕ СРАВНЕНИЯ')
      WRITE(4,14)
   14 FORMAT(1X,'ЧИСЛО БУКВ "A" НЕ РАВНО ЧИСЛУ БУКВ "B", ЧИСЛА')
      WRITE(4,15)
   15 FORMAT(1X,'"A" И "B" ВЗАИМНОПРОСТЫЕ.')
      WRITE(4,5)
      WRITE(4,6)
    6 FORMAT(1X,'КОЛИЧЕСТВО ТАКТОВ РАБОТЫ МТ')
      WRITE(4,*) TAKT
      CLOSE(4)
      END PROGRAM EVKLID 

Теперь, собственно, вопросы:
1) Знатокам Фортрана. Как сделать, чтобы палочки из файлов A.TXT и B.TXT считывались, будучи написанными в строчку (мне приходится их в столбик писать).
2) Программа отлично работает во всех случаях, кроме одного – когда числа (соответствующие словам) A и B, взаимно-простые. Тогда, по идее, на ленте должна остаться одна палочка, а остаётся больше. В последней конфигурации после сравнения (пример ниже) число символов A и B должно быть равным (принцип алгоритма Евклида). У меня этого в случае взаимно-простых чисел не наблюдается. Я могу это исправить «искусственно», но не хотелось бы выходить за рамки возможностей Машины Тьюринга.

[Николай]

Теперь пример работы. Если в файле A.TXT было 10 палочек, а в B.TXT 45 палочек (НОД=5), вот что моя машина пишет в файле результатов:

Цитата:

ИСХОДНАЯ ЗАПИСЬ НА ЛЕНТЕ
----||||||||||-|||||||||||||||||||||||||||||||||||||||||||||-----

ПЕРВАЯ КОНФИГУРАЦИЯ = X+Y
-----|||||||||||||||||||||||||||||||||||||||||||||||||||||||-----

КОНФИГУРАЦИЯ ПОСЛЕ СРАВНЕНИЯ
-----AAAAAAAAAABBBBBBBBBB|||||||||||||||||||||||||||||||||||-----


КОНФИГУРАЦИЯ ПОСЛЕ ВЫЧИТАНИЯ
---------------|||||||||||||||||||||||||||||||||||||||||||||-----

КОНФИГУРАЦИЯ ПОСЛЕ СРАВНЕНИЯ
---------------AAAAAAAAAABBBBBBBBBB|||||||||||||||||||||||||-----


КОНФИГУРАЦИЯ ПОСЛЕ ВЫЧИТАНИЯ
-------------------------|||||||||||||||||||||||||||||||||||-----

КОНФИГУРАЦИЯ ПОСЛЕ СРАВНЕНИЯ
-------------------------AAAAAAAAAABBBBBBBBBB|||||||||||||||-----


КОНФИГУРАЦИЯ ПОСЛЕ ВЫЧИТАНИЯ
-----------------------------------|||||||||||||||||||||||||-----

КОНФИГУРАЦИЯ ПОСЛЕ СРАВНЕНИЯ
-----------------------------------AAAAAAAAAABBBBBBBBBB|||||-----


КОНФИГУРАЦИЯ ПОСЛЕ ВЫЧИТАНИЯ
---------------------------------------------|||||||||||||||-----

КОНФИГУРАЦИЯ ПОСЛЕ СРАВНЕНИЯ
---------------------------------------------||||AAAAAABBBBB-----


КОНФИГУРАЦИЯ ПОСЛЕ ВЫЧИТАНИЯ
---------------------------------------------||||||||||----------

КОНФИГУРАЦИЯ ПОСЛЕ СРАВНЕНИЯ
---------------------------------------------AAAAABBBBB----------


КОНФИГУРАЦИЯ ПОСЛЕ ВЫЧИТАНИЯ
--------------------------------------------------|||||----------

ЕСЛИ В ПОСЛЕДНЕЙ КОНФИГУРАЦИИ ПОСЛЕ СРАВНЕНИЯ
ЧИСЛО БУКВ "A" НЕ РАВНО ЧИСЛУ БУКВ "B", ЧИСЛА
"A" И "B" ВЗАИМНОПРОСТЫЕ.

КОЛИЧЕСТВО ТАКТОВ РАБОТЫ МТ
1072

Извините, что очень длинно. Любые комментарии и советы приветствуются.