aboutsummaryrefslogtreecommitdiff
path: root/docs/posts/turing_complete_type_systems/index.html
diff options
context:
space:
mode:
Diffstat (limited to 'docs/posts/turing_complete_type_systems/index.html')
-rw-r--r--docs/posts/turing_complete_type_systems/index.html24
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 &nbsp 34 &nbsp
@@ -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> 48Traits</a></li>
49<li><a href="https://github.com/Ashymad/fortraith">A Forth
50implementation 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
53Turing complete system will ever stop. That is, it is impossible to
54write a program <code>f</code> that determines if a program
55<code>g</code>, where <code>g</code> is written in a Turing complete
56programming language, will ever halt. The <a
57href="https://en.wikipedia.org/wiki/Halting_problem">Halting Problem</a>
58is in fact, an <a
59href="https://en.wikipedia.org/wiki/Undecidable_problem">undecidable
60problem</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,
63compiles and infers types, I would describe it as a compiler inside a
64compiler. It is possible that <code>rustc</code> may never finish
65compiling your Rust program! I lied, <code>rustc</code> stops after a
66while, 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>