ecole42

ft_turing

ft_turing은 ecole42의 OCaml 프로젝트로, JSON 형식으로 정의된 튜링 머신을 읽어 실행하고 실행 과정을 단계별로 시각화하며 시간 복잡도를 분석하는 도구. OCaml의 함수형 프로그래밍 특성을 활용하여 튜링 머신의 상태 전이, 테이프 조작, 무한 루프 감지 등을 구현하며, 계산 이론과 알고리즘 복잡도 분석을 학습한다

OCaml
Functional Programming
GitHub

개요

ft_turing은 JSON 형식으로 정의된 튜링 머신을 읽어 실행하고, 실행 과정을 단계별로 시각화하며, 시간 복잡도를 분석하는 도구다.

주요 기능

  • 튜링 머신 시뮬레이션: JSON 파일로 정의된 튜링 머신을 실행
  • 실행 과정 시각화: 각 단계에서 현재 상태, 테이프 내용, 헤드 위치를 표시
  • 무한 루프 감지: 동일한 상태 구성을 반복하거나 무한 실행을 감지하여 중단
  • 시간 복잡도 분석: 실행 결과를 바탕으로 시간 복잡도를 자동 계산
  • 상태 방문 통계: 각 상태의 방문 횟수를 추적하여 분석

요구사항

  • OCaml (4.08 이상)
  • opam (OCaml 패키지 관리자)
  • dune (빌드 시스템)
  • yojson (JSON 파싱 라이브러리)

설치

1. 의존성 설치

make check_deps

또는 수동으로:

opam install ocamlfind yojson dune

2. 빌드

make

또는 dune을 사용하여:

dune build

사용법

./ft_turing <jsonfile> <input>

또는:

dune exec bin/main.exe -- <jsonfile> <input>

옵션

  • -h, --help: 도움말 메시지 출력

예제

./ft_turing res/0.unary_sub.json "111-11="

튜링 머신 JSON 형식

튜링 머신은 다음 형식의 JSON 파일로 정의된다:

{
  "name": "머신 이름",
  "alphabet": ["문자1", "문자2", ...],
  "blank": "빈 칸 문자",
  "states": ["상태1", "상태2", ...],
  "initial": "초기 상태",
  "finals": ["최종 상태1", "최종 상태2", ...],
  "transitions": {
    "상태1": [
      {
        "read": "읽을 문자",
        "to_state": "다음 상태",
        "write": "쓸 문자",
        "action": "LEFT" 또는 "RIGHT"
      },
      ...
    ],
    ...
  }
}

필드 설명

  • name: 튜링 머신의 이름
  • alphabet: 머신이 사용할 수 있는 모든 문자 목록
  • blank: 빈 칸을 나타내는 문자 (반드시 alphabet에 포함되어야 함)
  • states: 모든 상태 목록
  • initial: 초기 상태 (반드시 states에 포함되어야 함)
  • finals: 최종 상태 목록 (최소 하나 이상 필요, 모두 states에 포함되어야 함)
  • transitions: 상태별 전이 규칙
    • read: 현재 헤드 위치의 문자를 읽음
    • to_state: 전이할 다음 상태
    • write: 테이프에 쓸 문자
    • action: 헤드를 이동할 방향 ("LEFT" 또는 "RIGHT")

출력 형식

프로그램 실행 시 다음과 같은 정보가 출력된다:

  1. 머신 정보: 이름, 알파벳, 상태, 초기 상태, 최종 상태, 전이 규칙
  2. 실행 과정: 각 단계마다
    • 현재 테이프 내용 (헤드 위치는 하이라이트됨)
    • 현재 상태
    • 읽은 문자
    • 전이 정보 (다음 상태, 쓸 문자, 이동 방향)
  3. 실행 결과:
    • 총 실행 단계 수
    • 최대 방문 횟수를 가진 상태와 방문 횟수
    • 시간 복잡도 분석

시간 복잡도 계산

프로그램은 실행 결과를 바탕으로 다음과 같은 규칙으로 시간 복잡도를 계산한다:

  1. Infinite (무한): 실행 단계가 1,000,000 이상인 경우
  2. Linear (O(n)): 총 단계 수와 테이프 길이가 비슷한 경우
  3. Exponential (O(2^n)): 특정 상태의 방문 횟수가 테이프 길이의 두 배 이상인 경우
  4. Quadratic (O(n²)): 특정 상태의 방문 횟수가 테이프 길이 이상인 경우
  5. Constant (O(1)): 위의 조건을 만족하지 않는 단순한 상태 변화

에러 처리

프로그램은 다음 상황에서 에러를 감지하고 중단합니다:

  • 무한 루프: 동일한 (상태, 테이프, 헤드 위치) 구성을 반복하는 경우
  • 무한 실행: 빈 칸을 읽으면서 같은 상태에 머무는 경우가 연속으로 20회 이상 발생
  • 잘못된 문자: 테이프에 알파벳에 없는 문자가 발견된 경우
  • 전이 규칙 없음: 현재 상태와 읽은 문자에 대한 전이 규칙이 없는 경우

프로젝트 구조

ft_turing/
├── bin/                    # 실행 파일 소스 코드
│   ├── main.ml            # 메인 진입점 및 명령줄 인자 처리
│   ├── types.ml           # 튜링 머신 타입 정의
│   ├── parser.ml          # JSON 파싱 및 검증
│   ├── executer.ml        # 튜링 머신 실행 로직
│   └── print_machine.ml   # 머신 정보 출력
├── res/                    # 예제 튜링 머신 정의 파일
│   ├── 0.unary_sub.json   # 단항 뺄셈 예제
│   ├── 1.unary_add.json   # 단항 덧셈 예제
│   ├── 2.palindrome.json  # 회문 검사 예제
│   └── ...
├── test/                   # 테스트 파일
├── Makefile               # 빌드 스크립트
├── dune-project           # Dune 프로젝트 설정
└── ft_turing.opam        # OPAM 패키지 정의

예제 튜링 머신

프로젝트에는 여러 예제 튜링 머신이 포함되어 있다:

  • 0.unary_sub.json: 단항 표기법 뺄셈
  • 1.unary_add.json: 단항 표기법 덧셈
  • 2.palindrome.json: 회문 검사
  • 3.zero_n_one_n.json: 0^n1^n 패턴 인식
  • 4.zero_2n.json: 0^2n 패턴 인식
  • 5.utm_unary.json: 범용 튜링 머신 (단항 입력)

참고 자료

LinkedIn