이것은 중단 문제, 콜라 츠 추측 및 Kolmogorov 복잡성을 읽는 동안 내 마음에 떠오른 질문입니다. 나는 비슷한 것을 찾으려고했지만 특정 주제를 찾을 수 없었습니다. 아마도 그것이 큰 가치가 없거나 사소한 질문 일 수 있기 때문일 것입니다.
간단하게하기 위해 프로그램 / 기능의 세 가지 예를 들겠습니다.
function one(s):
return s
function two(s):
while (True):
print s
function three(s):
for i from 0 to 10^10:
print(s)
그래서 내 질문은 프로그램의 길이 (예 : 그것을 설명하는 데 사용되는 비트)와 프로그램이 사용하는 내부 메모리를 공식화하는 방법이 있다면 결정하는 데 필요한 최소 / 최대 시간 / 단계 수를 결정하는 것입니다. 프로그램이 종료되거나 영원히 실행되는지 여부.
예를 들어, 첫 번째 기능에서 프로그램은 내부 메모리를 변경하지 않고 일정 시간 후에 중지됩니다.
두 번째 예에서 프로그램은 영원히 실행되지만 프로그램은 내부 메모리도 변경하지 않습니다. 예를 들어, 상태를 변경하지 않는 프로그램 2와 동일한 길이의 모든 프로그램을 고려하면 단계의 상한을 결정할 수 없습니다.이를 초과하면이 프로그램이 절대 종료되지 않는다는 결론을 내릴 수 있습니까? (이유가 아니라면?)
마지막 예에서 프로그램은 상태 (변수 i)를 변경합니다. 따라서 각 단계에서 상한이 변경 될 수 있습니다.
[요약] Kolmogorov 복잡성은 텍스트와 같은 개체의 (설명 적) 복잡성을 찾는 방법을 제안합니다. 프로그램 (런타임에서 계산 됨)이 사용하는 메모리 공간을 설명하는 공식적인 방법을 고려할 때, 최대 단계 수를 계산할 수 있는지,이를 초과하면이 프로그램이 종료되는지 여부를 알 수 있는지 알고 싶습니다. 영원히 달려라.
마지막으로, 유용하다고 생각되는 출처를 제안하고 정확히 무엇을 찾고 있는지 파악하는 데 도움을 드리고 싶습니다.
감사합니다. (내 모국어가 아닌 영어에 대해 죄송합니다. 분명했으면 좋겠습니다)
결정 론적 튜링 머신이 정확히 동일한 구성을 두 번 입력하면 (지금까지 본 구성의 추적을 유지하면서 b를 감지 할 수 있음), TM이 영원히 반복된다는 것을 즉시 알 수 있습니다.
결정 론적 튜링 머신이 고정 된 일정량 이상의 입력 테이프를 사용할 수 없다는 것을 미리 알고있는 경우 TM은 명시 적으로 중지하거나 결국 이미 방문한 일부 구성을 입력해야합니다. TM이 최대 k 개의 테이프 셀을 사용할 수 있고 테이프 알파벳이 T이고 상태 집합이 Q라고 가정합니다. 그런 다음 (| T | +1) ^ k * | Q | 고유 한 구성 (길이 k x 상태 수의 문자열 수 (T 유니온 블랭크))과 pigeonhole 원칙에 따라 많은 단계를 수행하는 TM이 이전에 있었던 일부 구성에 들어가야한다는 것을 알고 있습니다.
하나 :이 함수가 내부 메모리를 사용하지 않는다는 사실이 주어 졌기 때문에 우리는 그것이 영원히 멈추거나 반복된다는 것을 압니다.
두 번째 :이 함수는 내부 메모리를 사용하지 않는다는 점이 주어 졌기 때문에 영원히 중단되거나 반복된다는 것을 알고 있습니다.
셋째 :이 함수는 고정 된 양의 내부 메모리 (34 비트와 같은)만을 사용하기 때문에 루프의 2 ^ 34 회 미만으로 TM이 주어진 입력에 대해 중지할지 여부를 알 수 있습니다.
이제 TM이 사용할 테이프 양 또는 프로그램이 사용할 메모리 양을 아는 것은 TM이 해결할 수있는 문제가 아닙니다. 그러나 메모리에 대한 정확한 고정 상한을 알려주는 오라클 (증명을 할 수있는 사람과 같은)이 있다면 중단 문제를 해결할 수 있습니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다