결정 불가능한 문제 목록

계산 가능성 이론에서, 결정 불가능한 문제는 예/아니오 대답을 요구하는 계산 문제의 한 종류이다. 그러나 항상 정답을 주는 컴퓨터 프로그램은 있을 수 없다. 즉, 가능한 프로그램은 때때로 틀린 답을 주거나 어떤 대답도 하지 않고 영원히 실행된다.좀 더 형식적으로 말하면, 결정 불가능한 문제는 언어가 재귀 집합이 아닌 문제입니다. 결정 가능한 언어 기사를 참조하십시오.헤아릴 수 없을 정도로 많은 문제가 있기 때문에 아래 목록은 불완전할 수밖에 없습니다.결정 불가능한 언어는 재귀적인 언어가 아니지만 튜링 인식 가능한 언어의 하위 집합일 수 있습니다. 즉, 그러한 결정 불가능한 언어는 재귀적으로 열거될 수 있습니다.

수학에서 결정 불가능한 많은 문제들은 단어 문제로 제기될 수 있다: 두 개의 구별되는 기호 문자열이 언제 같은 대상을 나타내는지 결정하는 것.

공리 수학의 결정 불가능성에 대해서는 ZFC에서 결정 불가능 문장의 목록을 참조하십시오.

논리상의 문제

• 힐베르트의 '엔셰이둥 문제'
• 2차 람다 미적분(또는 동등한 것)^[1]에 대한 유형 추론 및 유형 확인.
• 그래프 논리에서의 1차 문장이 유한 무방향 ^[2]그래프에 의해 실현될 수 있는지 여부를 판단한다.
• Trakhtenbrot의 정리 - 유한 만족도는 결정할 수 없다.
• 1차 호른 절의 만족도.

추상 시스템에 대한 문제

• 정지 문제(튜링 머신이 특정 입력에서 정지하는지 여부 결정)와 사망률 문제(모든 시동 구성에 대해 정지하는지 여부 결정)입니다.
• 튜링 기계가 바쁜 비버 챔피언인지 아닌지를 결정하는 것은(즉, 동일한 수의 상태와 기호를 가진 정지 튜링 기계 중 가장 오래 실행되는 것입니다).
• 라이스의 정리는 부분 함수의 모든 중요한 성질에 대해 주어진 기계가 그 성질을 가지고 부분 함수를 계산하는지 여부를 결정할 수 없다는 것이다.
• Minsky 머신의 정지 문제: 입력이 없는 유한 상태 오토마톤과 증가, 감소 및 제로 테스트가 가능한2개의 카운터가 있습니다.
• 비결정론적 푸시다운 자동화의 보편성: 모든 단어가 받아들여질지 여부를 결정합니다.
• 태그 시스템이 정지할지에 관한 문제.

행렬에 관한 문제

• 치명적인 행렬 문제: 정수 엔트리가 있는 n × n 행렬의 유한 집합이 주어졌을 때, 0 행렬을 산출하기 위해 어떤 순서로, 어쩌면 반복과 함께 곱할 수 있는지 여부를 결정한다.이것은 6개 이상의 3 × 3 행렬 집합 또는 2개의 15 ^[3]× 15 행렬 집합에서 결정할 수 없는 것으로 알려져 있다.
• 음이 아닌 정수 엔트리를 가진 상부 삼각 3 × 3 행렬의 유한 집합이 자유 반군을 생성하는지 여부를 결정한다.
• 정수 행렬의 최종 생성된 2개의 서브세그룹이 공통 요소를 가지고 있는지 여부를 판별한다.

조합군 이론의 문제

• 그룹에 대한 단어 문제.
• 켤레 문제.
• 그룹 동형상의 문제입니다.

토폴로지의 문제

• 두 개의 유한 단순 복합체가 동형인지 확인.
• 유한 단순 복합체가 다양체인지(다양체와 동형인지) 판단.
• 유한 단순 복합체의 기본군인지 아닌지를 결정하는 것은 사소한 일이다.
• 단순하게 연결되지 않은 두 개의 5-매니폴드가 동형인지 또는 5-매니폴드가 ^[4]S와⁵ 동형인지 판단한다.

분석상의 문제점

• 특정 클래스의 함수에 대해, 두 함수가 동일한지 여부를 결정하는 문제: 영등가성 문제(리처드슨의 [5]정리 참조), 함수의 영점; 함수의 무한 적분도 ^[6]클래스에 포함되는지 여부.물론, 이러한 문제의 일부 하위 분류는 결정될 수 있습니다.예를 들어 초월적 기본함수의 필드인 리슈 알고리즘에 속하는 기능의 기본적분을 위한 효과적인 결정절차가 있다.
• MRDP 정리가 힐베르트의 10번째 ^[6]문제를 해결한 결과, "기본적 자형함수의 명확한 등고선 배수 적분이 해석적인 모든 실제 분석 다양체에서 0인지 여부를 결정하는 문제".
• 형식의 상미분 방정식에 대한 해역 결정

${\displaystyle {frac}{dt}}=p(t,x),~x(t_{0})=x_{0}$

여기서 x는 R의 벡터ⁿ, p(t, x)는 t와 x의 다항식 벡터, 그리고 (t₀, x₀)는 ^[7]R에 속한다ⁿ⁺¹.

공식 언어 및 문법에 관한 문제

• Post 통신 문제.
• 문맥이 없는 문법이 가능한 모든 문자열을 생성하는지 또는 문맥이 모호한지를 판별합니다.
• 2개의 문맥이 없는 문법을 지정하면, 같은 문자열 세트를 생성하는지, 또는 한쪽이 다른 한쪽에서 생성된 문자열의 서브셋을 생성하는지, 또는 양쪽에서 생성되는 문자열이 있는지 여부를 판별할 수 있습니다.

기타 문제

• 주어진 Wang 타일 세트가 평면을 타일로 칠 수 있는지 확인하는 문제.
• 문자열의 Kolmogorov 복잡도를 결정하는 문제.
• 힐베르트의 열 번째 문제: 디오판틴 방정식(다변 다항식)이 정수에 해답을 가지고 있는지 여부를 결정하는 문제.
• 합리적인 좌표를 가진 주어진 초기 점이 주기적인지, 또는 그것이 주어진 열린 집합의 흡인 분지에 있는지, 2차원의 부분 선형 반복 지도에 있는지, 3차원의 ^[8]부분 선형 흐름에 있는지 여부를 결정하는 것.
• δ-calculus 공식에 정규 형식이 있는지 확인.
• 초기 패턴과 다른 패턴이 주어졌는지 여부에 대한 Conway의 Game of Life는 초기 패턴에서 후자의 패턴이 나타날 수 있습니다.
• 규칙 110 - 캔 속성 "X"가 나중에 나타나는 것과 관련된 대부분의 질문은 결정할 수 없습니다.
• 양자역학계에 스펙트럼 ^[9][10]갭이 있는지 여부를 판단하는 문제.
• 매직 게임에서 플레이어가 승리 전략을 가지고 있는지 판단: 개더링^[11]
• 부분적으로 관측 가능한 마르코프 결정 과정에서의 계획.
• 운임을 ^[12]고려할 때 한 목적지에서 다른 목적지로의 항공 여행을 계획하는 문제.

「 」를 참조해 주세요.

• 문제 목록
• 미해결 문제 목록
• 경감(복잡도)

메모들

참고 문헌

• Brookshear, J. 글렌(1989년).계산론:공식적인 언어, 자동자,과 복합성.캘리포니아 주 레드 우드시:Benjamin/Cummings PublishingCompany, Inc.부록 C알고리즘 만약 문법 위주의 모호함이 들어 있을지 결정하는 것으로 불가능한 일과 Halting의 문제 예로서, 알고리즘 프로그램 정확성 확인이 불가능한 경우를 포함한다.
• Halava, Vesa (1997). "Decidable and undecidable problems in matrix theory". TUCS technical report. 127. Turku Centre for Computer Science. CiteSeerX 10.1.1.31.5792. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
• Moret, B. M. E.; H. D. Shapiro (1991). Algorithms from P to NP, volume 1 - Design and Efficiency. Redwood City, California: Benjamin/Cummings Publishing Company, Inc. 제2장 "알고리즘 분석을 위한 수학적 기법"에서 기하급수적인 성능을 가진 알고리즘의 난해성에 대해 논의한다.
• Weinberger, Shmuel (2005). Computers, rigidity, and moduli. Princeton, NJ: Princeton University Press. 그룹의 문제라는 단어와 토폴로지의 다양한 문제에 대해 설명합니다.

추가 정보

• Poonen, Bjorn (2 April 2012), Undecidable problems: a sampler, arXiv:1204.0299, Bibcode:2012arXiv1204.0299P

외부 링크

• MathOverflow에서의 토론