비지 비버 함수와 정지 문제, 어떤 알고리즘으로도 계산할 수 없는 수가 존재하는 이유
모든 계산 가능한 함수보다 빠르게 자라는 비지 비버 함수를 따라가며, 튜링 머신의 정지 문제와 골드바흐 추측이 어떻게 얽히는지, 그리고 수학이 어느 지점부터 답할 능력을 잃는지 짚어본 해설 영상을 정리했다.
핵심 내용 읽기 →
AI TOPIC
계산 이론 최신 뉴스와 핵심 해설
계산 이론 관련 핵심 뉴스와 활용 인사이트 4편을 최신순으로 모았습니다.
비지 비버 함수와 정지 문제: 튜링 기계가 드러내는 계산의 한계와 콜라츠 추측의 연결
튜링 기계로 정의한 비지 비버 함수는 어떤 계산 가능한 함수보다 빠르게 커진다. 콜라츠 추측과의 연결, 골드바흐 추측을 유한 계산으로 바꾸는 시프트 함수, 그리고 수학이 끝내 증명할 수 없는 지점까지 짚는다.
핵심 내용 읽기 →
트랜스포머 LLM 튜링 완전성 논쟁: 생각의 사슬이 언어 모델을 확률적 튜링 기계로 만드는 이유
취리히연방공대 연구자 프란츠 노박과의 대담. 촘스키 위계부터 트랜스포머 인코더와 디코더의 표현력 차이, 생각의 사슬이 언어 모델을 확률적 튜링 기계와 동등하게 만드는 증명, 그리고 학습 가능성의 벽까지 풀어 설명한다.
핵심 내용 읽기 →
촘스키 위계 쉽게 이해하기: 정규·문맥자유·문맥의존·무제한 문법과 필요한 메모리
네 종류의 문법이 각각 어떤 계산 기계와 메모리를 필요로 하는지 촘스키 위계로 설명한다. 정규 문법의 유한 상태부터 문맥자유의 스택, 문맥의존의 제한된 테이프, 무제한 문법의 튜링 완전성까지 한눈에 정리했다.
핵심 내용 읽기 →