new post: turing complete type systems

1 files changed, 22 insertions, 0 deletions

diff --git a/posts/turing_complete_type_systems.md b/posts/turing_complete_type_systems.md
new file mode 100644
index 0000000..b6ec7bc
--- /dev/null
+++ b/posts/turing_complete_type_systems.md
@@ -0,0 +1,22 @@
+Rust's type system is Turing complete:
+
+ - [FizzBuzz with Rust Traits](https://github.com/doctorn/trait-eval/)
+ - [A Forth implementation with Rust Traits](https://github.com/Ashymad/fortraith)
+
+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](https://en.wikipedia.org/wiki/Halting_problem) is
+in fact, an [undecidable
+problem](https://en.wikipedia.org/wiki/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 understand that this post lacks content.