튜링 머신

컴퓨터 과학의 핵심 개념

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

오토마타에서 튜링 머신으로

  • 유한 오토마타: 메모리 제한, 정규 언어 처리.
  • 푸시다운 오토마타: 스택 기반 메모리, 문맥 자유 언어 처리.
  • 튜링 머신: 무한 테이프(무제한 메모리), 계산 가능한 모든 문제 해결.

앨런 튜링의 일러스트

컴퓨터 과학의 핵심 개념

튜링 머신이란?

튜링 머신이 어떻게 동작하는지 보여주는 도식

튜링 머신

  • 무한 테이프를 가진 추상 기계.
  • 기호를 읽고 쓴다.
  • 어떤 알고리즘이든 모사 가능.
컴퓨터 과학의 핵심 개념

비유로 보는 튜링 머신

튜링 머신의 비유로, 주방에서 요리사가 레시피대로 요리하는 그림

주방과 요리사 = 튜링 머신

  • 조리대는 테이프.
  • 조리대 구획은 셀.
  • 재료는 기호.
  • 요리사는 헤드로서 읽고 쓴다.
  • 레시피 책은 과정을 안내하는 프로그램.
컴퓨터 과학의 핵심 개념

튜링 머신이 중요한 이유

튜링 머신과 계산 가능성

  • 모든 알고리즘을 모사 가능
  • 컴퓨터가 풀 수 있는 한계를 규정
  • 결정 불가능 문제 개념 제시(예: 정지 문제)
  • 현대 계산 이론의 기초 마련
컴퓨터 과학의 핵심 개념

정지 문제

  • 질문: 특정 입력에 대해 프로그램이 멈출지 영원히 실행될지 예측할 수 있는가?
  • 튜링의 통찰: 이를 모든 프로그램에 대해 해결하는 범용 알고리즘은 없다.
  • 결과: 정지 문제는 결정 불가능, 어떤 문제들은 알고리즘 해가 없다.
  • 함의: 계산 한계는 암호학과 AI에 영향

정지 문제가 무엇인지 보여주는 도식

컴퓨터 과학의 핵심 개념

연습해 봅시다!

컴퓨터 과학의 핵심 개념

Preparing Video For Download...