From 3739ce5d1969df71f272d18a3ff8b5e13cd27f4f Mon Sep 17 00:00:00 2001 From: Akshay Date: Thu, 18 Jun 2020 10:39:57 +0530 Subject: new post: turing complete type systems --- posts/turing_complete_type_systems.md | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) create mode 100644 posts/turing_complete_type_systems.md (limited to 'posts') 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. -- cgit v1.2.3