diff options
Diffstat (limited to 'docs/posts/turing_complete_type_systems/index.html')
-rw-r--r-- | docs/posts/turing_complete_type_systems/index.html | 24 |
1 files changed, 19 insertions, 5 deletions
diff --git a/docs/posts/turing_complete_type_systems/index.html b/docs/posts/turing_complete_type_systems/index.html index 1f6fd4c..2a9361e 100644 --- a/docs/posts/turing_complete_type_systems/index.html +++ b/docs/posts/turing_complete_type_systems/index.html | |||
@@ -28,7 +28,7 @@ | |||
28 | 18/06 — 2020 | 28 | 18/06 — 2020 |
29 | <div class="stats"> | 29 | <div class="stats"> |
30 | <span class="stats-number"> | 30 | <span class="stats-number"> |
31 | 9.18 | 31 | 9.19 |
32 | </span> | 32 | </span> |
33 | <span class="stats-unit">cm</span> | 33 | <span class="stats-unit">cm</span> |
34 |   | 34 |   |
@@ -44,12 +44,26 @@ | |||
44 | <div class="post-text"> | 44 | <div class="post-text"> |
45 | <p>Rust’s type system is Turing complete:</p> | 45 | <p>Rust’s type system is Turing complete:</p> |
46 | <ul> | 46 | <ul> |
47 | <li><a href="https://github.com/doctorn/trait-eval/">FizzBuzz with Rust Traits</a></li> | 47 | <li><a href="https://github.com/doctorn/trait-eval/">FizzBuzz with Rust |
48 | <li><a href="https://github.com/Ashymad/fortraith">A Forth implementation with Rust Traits</a></li> | 48 | Traits</a></li> |
49 | <li><a href="https://github.com/Ashymad/fortraith">A Forth | ||
50 | implementation with Rust Traits</a></li> | ||
49 | </ul> | 51 | </ul> |
50 | <p>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 <code>f</code> that determines if a program <code>g</code>, where <code>g</code> is written in a Turing complete programming language, will ever halt. The <a href="https://en.wikipedia.org/wiki/Halting_problem">Halting Problem</a> is in fact, an <a href="https://en.wikipedia.org/wiki/Undecidable_problem">undecidable problem</a>.</p> | 52 | <p>It is impossible to determine if a program written in a generally |
53 | Turing complete system will ever stop. That is, it is impossible to | ||
54 | write a program <code>f</code> that determines if a program | ||
55 | <code>g</code>, where <code>g</code> is written in a Turing complete | ||
56 | programming language, will ever halt. The <a | ||
57 | href="https://en.wikipedia.org/wiki/Halting_problem">Halting Problem</a> | ||
58 | is in fact, an <a | ||
59 | href="https://en.wikipedia.org/wiki/Undecidable_problem">undecidable | ||
60 | problem</a>.</p> | ||
51 | <p><em>How is any of this relevant?</em></p> | 61 | <p><em>How is any of this relevant?</em></p> |
52 | <p>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 <code>rustc</code> may never finish compiling your Rust program! I lied, <code>rustc</code> stops after a while, after hitting the recursion limit.</p> | 62 | <p>Rust performs compile-time type inference. The type checker, in turn, |
63 | compiles and infers types, I would describe it as a compiler inside a | ||
64 | compiler. It is possible that <code>rustc</code> may never finish | ||
65 | compiling your Rust program! I lied, <code>rustc</code> stops after a | ||
66 | while, after hitting the recursion limit.</p> | ||
53 | <p>I understand that this post lacks content.</p> | 67 | <p>I understand that this post lacks content.</p> |
54 | 68 | ||
55 | </div> | 69 | </div> |