FOST 내부에 콤팩트 한 형태로 Rayo 함수를 작성하는 방법이 없다는 것을 증명

FOST에 Rayo 함수를 작성할 수 있다고 가정합니다. 그렇다면 Rayo (Rayo (i))를 FOST에 쓰기보다는 작은 문자를 사용하여 작게 표현할 수 있습니다 (10 억자를 필요로하는 경우). 이제 j를 Rayo (Rayo (i))를 나타낼 수있는 충분히 큰 수로 취합니다. 그러나 Rayo (i)보다 크지는 않습니다. i 즉, j 개의 문자가있는 FOST는 Rayo (Rayo (i))를 쓸 수 있습니다.

그런 다음 jo와 함께 FOST가 Rayo (Rayo (i)), Rayo (j)> Rayo (Rayo (i))를 설명 할 수 있으므로 Rayo 함수의 정의에 따라 Rayo 함수가 증가함에 따라, Rayo (j)> Rayo (Rayo (i))는 j> Rayo (i)를 의미합니다.

이것은 모순이다. 왜냐하면 우리는 j

QED

이 증명에서 알 수 있듯이, Rayo (Rayo (i))를 작성하기 위해서는 FOST의 Rayo (i) 문자가 필요합니다. 이것은 전혀 컴팩트 한 표현이 아닙니다. 따라서 라오 함수를 작성하는 컴팩트 표현식이 존재하지 않습니다.

이 증명을 읽음으로써 Rayo 함수 자체가 모순을 가지고 있으며 정의가 잘못되었다고 느낄 수 있습니다. 그러나 사실이 아닙니다. FOST의 모순 된 표현을 제공하면 유효한 표현식에서 제외되어 지정된 번호의 이름을 지정합니다. Rayo는 임의의 모순을 제외 할 수 있도록 Rayo 번호를 정의했습니다. Rayo (i) 따라서 걱정하지 마십시오. Rayo의 번호는 잘 정의되어 있습니다.

Rayo 함수를 oracle f로 구현함으로써, 간단히 f (f (i))로 Rayo (Rayo (i))를 작성할 수 있습니다 (공식 표현은 좀 더 복잡합니다). Rayo와 Rayo는 서로 다른 기능이기 때문에 j Rayo 2 를 구현 하려면 원래 FOST와는 다른 FOST를 정의해야합니다. 이것이 Rayo 함수 자체를 구현하기 위해 oracle formula가 필요한 이유입니다. Rayo 2 (i), Rayo n 또는 Rayo (i)의 재귀 함수를 OFOST (oracle-implemented FOST)로 작성할 수 있습니다. 따라서 OFOST를 사용한 Rayo 함수는 FOST의 Rayo 함수보다 훨씬 강력합니다. 이것은 단지 시작과 R [2] 수준입니다. F 7 은 R [φ 2(0)], 따라서 Rayo 함수보다 훨씬 강력합니다.


  • 비 계산.
  • F 7 (X)의 R을 = φ 2 (0)].