트랜스컴퓨팅 문제

Transcomputational problem

계산 복잡성 이론에서, 트랜스 컴퓨팅 문제는 10비트93 이상의 정보를 처리해야 하는 문제다.[1]10보다93 큰 숫자는 트랜스컴퓨팅 숫자라고 불린다.브레머만의 한계라고 불리는 숫자 10은93 한스-조아힘 브레머만(Hans-Joachim Bremermann)에 따르면 지구의 추정연령과 동일한 기간 내에 지구 크기 크기의 가상 컴퓨터에 의해 처리되는 총 비트 수입니다.[1][2]트랜스컴퓨팅이라는 용어는 브레머만에 의해 만들어졌다.[3]

예

집적 회로 테스트

309개의 부울 입력과 1개의 출력으로 집적회로의 모든 조합을 철저히 시험하려면 총 2개의309 입력 조합에 대한 시험이 필요하다.숫자 2는309 트랜스컴퓨팅 숫자(즉, 10보다93 큰 숫자)이기 때문에, 그러한 집적회로의 시스템을 테스트하는 문제는 트랜스컴퓨팅 문제다.이것은 어떤 사람이 짐승의 힘만으로 입력의 모든 조합에 대해 회로의 정확성을 검증할 수 있는 방법이 없다는 것을 의미한다.[1][4]

패턴인식

체스보드 유형의 q×q 배열을 고려해 보십시오. 체스보드 유형의 각 정사각형은 k 색 중 하나를 가질 수 있다.전체적으로 kn 컬러 패턴이 있는데 여기서 n = q2.몇몇 선택된 기준에 따라 패턴의 최선의 분류를 결정하는 문제는 가능한 모든 색상 패턴을 검색하는 것으로 해결될 수 있다.두 가지 색상의 경우, 그러한 검색은 어레이가 18×18 이상일 때 트랜스컴퓨팅이 된다.10×10 어레이의 경우, 9개 이상의 색상이 있을 때 문제가 트랜스컴퓨팅이 된다.[1]

이것은 망막의 생리학적 연구와 어느 정도 관련이 있다.망막에는 약 100만 개의 빛에 민감한 세포가 들어 있다.각 세포에 대해 가능한 상태(예를 들어 활성 상태와 비활성 상태)가 두 개뿐이었더라도 전체적으로 망막 처리에는 10비트300,000 이상의 정보가 필요하다.이것은 브레머만의 한계를 훨씬 넘는 것이다.[1]

일반 시스템 문제

각각 k개의 다른 상태를 취할 수 있는 n개의 변수 시스템은 k개의n 가능한 시스템 상태를 가질 수 있다.이러한 시스템을 분석하기 위해서는 최소 kbit의n 정보가 처리되어야 한다.문제는n k > 10이93 되면 트랜스컴퓨팅이 된다.이러한 현상은 k와 n의 다음 값에서 발생한다.[1]

k 2 3 4 5 6 7 8 9 10
n 308 194 154 133 119 110 102 97 93

시사점

실제적인 컴퓨터 변환 문제의 존재는 컴퓨터라는 한계를 데이터 처리 도구로서 내포하고 있다.이 점은 브레머만 자신의 말로 가장 잘 요약된다.[2]

"문제 해결, 정리 증명, 패턴 인식에 힘쓰는 다양한 그룹의 경험들이 모두 같은 방향을 가리키는 것 같다.이 문제들은 어렵다.한 번에 우리의 모든 문제를 해결할 수 있는 왕로나 간단한 방법은 없는 것 같다.데이터 처리 속도와 양에 대한 궁극적인 한계에 대한 나의 논의는 다음과 같이 요약될 수 있다: 엄청난 수의 가능성을 수반하는 문제는 단순히 데이터 처리 양으로도 해결되지 않을 것이다.우리는 우리가 생각할 수 있는 모든 독창성을 위해 품질, 정제, 속임수를 찾아야만 한다.오늘날의 컴퓨터보다 빠른 컴퓨터는 큰 도움이 될 것이다.우리는 그것들이 필요할 것이다.하지만, 우리가 원칙적으로 문제에 대해 걱정할 때, 오늘날의 컴퓨터는 거의 언제나처럼 빠르다.
우리는 데이터 처리 기술이 일반 기술이 그랬던 것처럼 단계적으로 진행될 것으로 기대할 수 있다.특정 문제에 적용되는 독창성에 대한 무한도전이 있다.무수한 세부사항을 정리하기 위해 일반적 개념과 이론도 끝없이 필요하다."

소설로

더글러스 애덤스의 '은하를 향한 히치하이커의 안내서'에서 지구는 슈퍼컴퓨터로, '생명과 우주와 모든 것의 극한 질문'(그 답은 42로 알려져 있다)으로 알려진 문제를 계산하기 위해 고안된 것이다.[5]

참고 항목

참조

  1. ^ a b c d e f Klir, George J. (1991). Facets of systems science. Springer. pp. 121–128. ISBN 978-0-306-43959-9.
  2. ^ a b 브레머만, H.J. (1962) 진화 및 재조합을 통한 최적화 in: 자체 조직 시스템 1962, M.C. 요빗스 외, 스파르타 북스, 워싱턴 D.C. 페이지 93–106을 편집했다.
  3. ^ Heinz Muhlenbein. "Algorithms, data and hypotheses : Learning in open worlds" (PDF). German National Research Center for Computer Science. Retrieved 3 May 2011.
  4. ^ Miles, William. "Bremermann's Limit". Retrieved 1 May 2011. 소스가 입력 수로 308을 사용하는 반면, 이 숫자는 오류: 2308 < 10에93 근거한다.
  5. ^ 은하계 히치하이커 안내서의 장소 보기