x86의 mov 명령만으로 컴파일러 만들기

해커뉴스[1]에서 재미있는 이야기를 봤다.

Turing complete란 튜링 머신과 동등한 작업을 할 수 있는 성질을 말한다는데, 뭐 본인의 전공이 아니라 잘 모른다. ㅋ

Turing complete한 머신들은 다양한 종류가 알려져 있다고 하는데, 심지어 (아마 지적 유희의 일환으로) 하나의 명령어만으로 작동하는 Turing complete한 컴퓨터를 생각할 수도 있다. 이런 가상의 머신을 ‘궁극의 축소 명령어 집합 컴퓨터(ultimate reduced instruction set computer)‘라고 한다나 뭐라나-_-

실제로 x86의 mov 명령어만으로도 Turing complete하다는 것이 증명가능하다고 하는데, 케임브리지 대학의 Stephen Dolan의 논문[2]에 증명이 있다고 한다. 근데 뭐 본인은 논문의 앞부분이랑 끝부분만 봤기 때문에 증명의 과정은 잘 모르겠다. ㅋ

이 논문[2]의 말미에는 오직 mov 명령만으로 아마 컴파일러를 만들 수 있겠지라고 영국식 농담 비스무리하게 써 놓았는데, 그걸 실제로 실행한 친구[3]가 있어서 해커뉴스에서 화제가 된 것. 음… 뭔가 잉여로움이 느껴진다.

뭐 본인은 능력부족으로 직접 실행해보거나 소스코드를 검사해보지는 않았다. ㅎㅎ

 


[1] https://news.ycombinator.com/item?id=9751312
[2] http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf
[3] https://github.com/xoreaxeaxeax/movfuscator

2 thoughts on “x86의 mov 명령만으로 컴파일러 만들기

  1. MOV로 실시간으로 코드를 주무르나보다 하고 논문을 봤더니 그건 아니군요. “우린 그런 치팅은 하지 않아”라니… ㅋ 순수하게 메모리 영역을 조작해서 브랜칭을 구현하는 대신 코드 마지막에 처음으로 돌아가는 unconditional jump 한 번이 있고, halt는 0번지 메모리를 읽으려고 시도하는 걸로 일으키네요.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중