Skip to content

Proof of turing completeness

Jaeyong Sung edited this page Mar 11, 2020 · 1 revision

A finite pushdown automaton with 2 stacks is same with a turing machine. It means that it is turing complete. First you can easily know that hyeong language is a finite automaton. Second you can have 2 stacks and move the elements freely. Third let's prove that hyeong language is a pushdown automaton. The state is decided by the input and the elements in the current stack. The operation of hyeong language use the top of the current stack. So the state is decided by the input and the current stack's top. And it has a finite set's of input and stacks. So the hyeong language is a finite pushdown automaton with more than 2 stacks. So it is turing complete. In detail, you can easily design the hyeong language to perform the multitape turing machine. The multitape turing machine can represent the turing machine so the hyeong language can represent the turing machine. So it is turing complete. Another proof is using the SKI Calculus. It is known that the SKI Calculus is turing complete. (TODO)

Clone this wiki locally