우리가 무엇인지 모르지만 아마도 존재하는 알고리즘이 있습니까? 수학에는 비 구조적인 존재

수학에는 비 구조적인 존재 증명이 많이 있으므로, 그것을 찾는 방법을 모르더라도 특정 객체가 존재한다는 것을 알고 있습니다.

컴퓨터 과학에서 비슷한 결과를 찾고 있습니다. 특히, 알고리즘을 보여주지 않고 결정할 수 있다는 문제가 있습니까? 즉, 알고리즘으로 해결할 수 있다는 것을 알고 있지만 알고리즘이 어떻게 보이는지 모릅니다.



답변

가장 간단한 경우는 존재하는 알고리즘을 알고 있지만 어떤 알고리즘은 알려 진지 모르지만 유한 상태 오토마타와 관련이 있습니다.

언어의 L 1 언어에 의해 L (2) 로 정의된다 L 1 / L 2 = { X | Y L  되도록  X의 Y L 1 } .

L1/L2

L1

L2

L1/L2={x∣∃y∈L2 such that xy∈L1}

규칙적인 세트가 임의의 세트에 의해 몫 아래에서 닫히는 것이 쉽게 증명됩니다. 다시 말해, 이 규칙적이고 L 2 가 임의적 일 필요는 없지만 (반드시 규칙적인 것은 아님), L 1 / L 2 역시 규칙적입니다.

L1

L2

L1/L2

증거는 매우 간단합니다. 하자 정규 세트 받아들이 FSA 수 R , QF는 각각의 상태의 설정 및 수용 상태의 세트이다, 그리고하게 L은 임의의 언어가 될. F = { q Q y L 이라고하자

M=(Q,Σ,δ,q0,F)

R

Q

F

L

L 의 문자열을 수락하여 최종 상태에 도달 할 수있는 상태 집합입니다.

F′={q∈Q∣∃y∈Lδ(q,y)∈F}

L

오토 마톤 과 다르다 M
에만 세트 F 의 최종 상태를 정확하게 인식 R / L . (또는이 사실에 대한 증거는 Hopcroft-Ullman 1979, 62 페이지를 참조하십시오.)

M′=(Q,Σ,δ,q0,F′)

M

F′

R/L

그러나, 세트 이 결정 불가능한 경우, F 를 정의하는 특성을 갖는 상태를 결정하는 알고리즘이 없을 수있다 . 따라서 우리는 집합 F Q 의 부분 집합 이라는 것을 알고 있지만 어떤 부분 집합을 결정하는 알고리즘은 없습니다. 결과적으로 R2 | Q | 가능한 FSA, 우리는 그것이 무엇인지 모릅니다. 고백해야하지만 우리는 그것이 어떻게 생겼는지 대부분 알고 있습니다.

L

F′

F′

Q

R

2|Q|

이것은 때로는 거의 건설적인
증거 라고 불리는 것의 예입니다. 즉 유한 한 수의 답변 중 하나가 옳다는 증거입니다.

나는 그 확장이 열거 가능한 대답 세트 중 하나가 옳다는 증거 일 수 있다고 생각합니다. 그러나 나는 모른다. 예를 들어 모순 만 사용하는 것과 같이 어떤 문제를 결정할 수 있다는 순수한 비 구조적인 증거도 알지 못합니다.


답변

헨드릭의 원래 의견을 확대하려면이 문제를 고려하십시오.

n≥0

n

π

이 문제는 다음 두 경우 중 하나를 얻을 수 있기 때문에 결정 가능합니다.


  1. N

    π

    N


  2. n

    π

    n

(1) 문제에 대한 결정 알고리즘은 다음 중 하나입니다.

n>N

(2) 경우 알고리즘은

“예”라고 대답하십시오.

이들 각각은 분명히 결정 알고리즘입니다. 우리는 단지 어느 것을 모른다. 그러나 결정 가능성 은 알고리즘 의 존재 를 요구하기 때문에 어떤 알고리즘을 사용할 것인지 지정하지 않기 때문에 충분하다 .


답변

여기에 답이 없습니다. 나는 그것이 반대라고 주장하고 @sdcwc가 실수를 지적하기 전에 8 명의 사람들이 공의에 찬성하기로 동의했기 때문에 그것이 유익하다고 생각하기 때문에 게시하고 있습니다. 나는 그들이 틀렸다는 것을 알면 많은 사람들이 그것을 올렸을 지 확신하지 못하기 때문에 첫 번째 답변을 편집하고 싶지 않았습니다.

S

S

H

H