Turing Complete Type Systems
Rust’s type system is Turing complete:
It is impossible to determine if a program written in a generally Turing complete system will ever stop. That is, it is impossible to write a program f
that determines if a program g
, where g
is written in a Turing complete programming language, will ever halt. The Halting Problem is in fact, an undecidable problem.
How is any of this relevant?
Rust performs compile-time type inference. The type checker, in turn, compiles and infers types, I would describe it as a compiler inside a compiler. It is possible that rustc
may never finish compiling your Rust program! I lied, rustc
stops after a while, after hitting the recursion limit.
I understand that this post lacks content.
I'm Akshay, I go by nerd or nerdypepper on the internet.
I am a compsci undergrad, Rust programmer and an enthusiastic Vimmer. I write open-source stuff to pass time. I also design fonts: scientifica, curie.
Send me a mail at nerdy@peppe.rs or a message at nerdypepper@irc.rizon.net.