현재는 한 줄에 최대 1000글자 제한밖에 없는데, 이는 문제로서 성립하기에 너무나도 부족합니다.
- SK combinatory logic은 Turing-complete하기 때문에 당연히 무한 루프가 발생할 수 있고, 가장 잘 알려진 무한 루프(SII(SII))를 만드는 데에 40글자면 충분합니다. 따라서 입력 조건에 "모든 주어진 식은 유한 시간 내에 종료된다" 조건이 필요합니다.
- λx.x x는 Church numeral x를 입력으로 받아 x^x(x의 x승)를 계산하는 함수입니다. 이를 Church numeral 2에 세 번만 반복 적용하면 출력 길이를 적어도 256^256으로 만들 수 있습니다. 뒤에 S K를 붙여서 S(S(S(...(SK)...))) 꼴로 reduction을 강제하면 연산 횟수도 최소 256^256번이 됩니다. 이러한 식의 글자 수는 겨우 91글자입니다. 따라서, "연산 횟수"와 "출력 길이", 그리고 "연산 도중에 나타나는 모든 식의 길이의 최댓값"과 같은 조건이 추가로 필요할 것으로 생각됩니다.
bubbler 10일 전 3
현재는 한 줄에 최대 1000글자 제한밖에 없는데, 이는 문제로서 성립하기에 너무나도 부족합니다.
- SK combinatory logic은 Turing-complete하기 때문에 당연히 무한 루프가 발생할 수 있고, 가장 잘 알려진 무한 루프(SII(SII))를 만드는 데에 40글자면 충분합니다. 따라서 입력 조건에 "모든 주어진 식은 유한 시간 내에 종료된다" 조건이 필요합니다.
- λx.x x는 Church numeral x를 입력으로 받아 x^x(x의 x승)를 계산하는 함수입니다. 이를 Church numeral 2에 세 번만 반복 적용하면 출력 길이를 적어도 256^256으로 만들 수 있습니다. 뒤에 S K를 붙여서 S(S(S(...(SK)...))) 꼴로 reduction을 강제하면 연산 횟수도 최소 256^256번이 됩니다. 이러한 식의 글자 수는 겨우 91글자입니다. 따라서, "연산 횟수"와 "출력 길이", 그리고 "연산 도중에 나타나는 모든 식의 길이의 최댓값"과 같은 조건이 추가로 필요할 것으로 생각됩니다.