CS 지식/알고리즘 (1) 썸네일형 리스트형 [알고리즘] HALTING Problem decision problem 컴퓨터 알고리즘에서 decision problem(결정 문제, 판정 문제)란 특정 입력에 대해 예-아니로 답이 있는 문제를 의미한다.이는 알고리즘 이론과 복잡도 이론에서 중요한 개념 중 하나이다. Halting Problemhalting problem(정지 문제)는 decision problem의 한 갈래로, "주어진 프로그램이 해결하고자 하는 문제가 해결 가능한지 말해줄 수 있는 일반화된 알고리즘이 존재하는가?" 라는 질문이다. 문제 정의프로그램 M과 입력 X가 있을 때, M에 입력 X를 시키면 종료할 것인가?M(X): 프로그램 M에 입력 X를 주고 실행시킨 상태사람이 문제를 푼다고 생각하고, M과 X가 모두 문자열이라 가정한다.모든 경우에 해결이 돼야한다.M(X)는 종.. 이전 1 다음
