셋의 가산성과 계산 가능성의 동등성

"가산 집합"의 개념은 1874년 가산 집합과 비가산 집합의 경계를 설정한 Georg Cantor에 의해 제시되었습니다. "계산 가능한 집합"의 개념은 1930년대에 컴퓨터 과학의 창립자들인 Church와 Turing에 의해 계산 모델 연구에서 발생했습니다. 그러나 가산성과 계산 가능성 간의 연결성은 지난 80년간 철저히 연구되지 않았습니다. 집합 S의 가산 전단사(bijection)는 자연수의 집합에서 S로의 전단사입니다. S가 유한하거나 S에 계산 가능한 가산 전단사가 존재할 경우 S는 열거 가능하다고 말합니다. 우리는 S가 열거 가능할 필요조건이자 충분조건이 S가 계산 가능하다는 것을 증명합니다. 이 동등성은 집합론 및 계산 가능성 이론 연구에 통찰력을 제공하며, 가산성의 개념이 공간 및 시간 복잡성과 관련이 있음을 드러냅니다. 우리는 전체 계산 가능한 함수(또는 결정자, 알고리즘)의 집합이 열거 불가능함을 보여줍니다. 또한 우리가 열거 가능하도록 집합에 대한 충분하고 필요한 조건을 제공하며, 특정 집합이 열거 불가능한 이유를 설명하기 위해 계산 순서 개념을 사용합니다. "가산 집합의 모든 부분 집합은 가산하다" 또는 "모든 형식 언어는 가산하다"와 같은 가산 집합에 대한 몇 가지 유명한 명제들이 유효한 증명이 부족함을 보여줍니다. 이러한 입증되지 않은 명제들은 이산 수학, 집합론, 계산 가능성 이론에 대한 대학 강의에서 널리 가르쳐지고 있습니다.