Turing & The Halting Problem - Computerphile

Comments · 1.7K

• CA

  @CatnamedMittens · 10 years ago

  Deepest V neck of all time.

  3K

• RU

  @rupert1909 · 6 years ago

  I did a depth-first search on this page, it returned his V-neck.

  133

• YA

  @Yaxqb · 5 years ago

  <a href="https://www.youtube.com/watch?v=macM_MtS_w4&amp;t=158">2:38</a> when he said &quot;Think about your computer running&quot;, my network froze and started buffering the video!! Thought it was some kind of joke!! Computerphile never fails to make me smirk

  74

• MT

  @mthai66 · 2 years ago

  Turing didn&apos;t invent a computer program to demonstrate that a particular something was impossible, he invented the entire idea of computers and programs for the purpose of showing that this something was impossible. Think about that for a moment.

  31

• MS

  @msironen · 12 years ago

  What&apos;s also interesting is if you could build an &quot;oracle&quot; (ie a machine that solves the halting problem), you could use it to immediately solve many unsolved mathematical problems, such as the Goldbach conjecture or the Twin Prime conjecture. Simply make a program that starts looping integers and halts if it finds an integer where the conjecture doesn&apos;t hold. Normally doing this would be useless since you&apos;d have to run it forever, but if you had an oracle you could simply input into the oracle and it&apos;d immediately tell you if it ever halted and if it did, conjecture is false; otherwise it&apos;s true.

  274

• AR

  @arnoclaude317 · 7 years ago

  When someone asks whether h+ halts or not:<br>Well yes, but actually, no.

  179

• HU

  @HumanRights4Everyone · 10 years ago

  What if it simultaneously halts and doesn&apos;t halt until it is observed?

  838

• JO

  @joebrooks370Z · 11 years ago

  I think some people who aren&apos;t understanding the problem. The problem isn&apos;t &quot;Can I write a program that will halt every time I run it?&quot; or &quot;Can I determine if my specific program X comes to a halt?&quot; (trivial examples are easy to come by). The question people were considering at the time was, &quot;If we could create Turing machines (you can read &quot;computer&quot; for &quot;Turing Machine&quot; in most senses) which accept an input and give an output, will they be able to solve any problem put them, or will there be problems which the machine will not be able to solve?&quot; It needs to be understood that if your hypothesis is that &quot;ALL problems given to the Turing Machine can be solved by the Turing Machine&quot;, then to disprove this hypothesis, you only have to come up with ONE counterexample. To demonstrate that there are SOME problems that a Turing Machine will not be able to solve, he created the halting problem. Somewhat trivial examples are being used to demonstrate that a contradiction occurs and the program would never halt (and therefore never return an answer to the problem), but the halting problem is a specific problem that cannot be solved. Basically, the point is that for the halting problem, for any given halting program of any complexity, an input can always be devised such that you can cause a halting program to eat itself and go into an infinite loop. As you only need one counter-example to prove that a Turing Machine cannot solve ALL problems, this is considered a proof that there are limitations to what can be proven in any formalized system, such as a Turing Machine, or as with Gödel&apos;s Theorem, arithmetic with natural numbers.

  737

• WI

  @wingsandstache · 10 years ago

  What would happen if pinocchio said: My nose will grow

  327

• CH

  @ChaosPootato · 12 years ago

  I love how there&apos;s tea and cups behind him :D

  43

• AR

  @archidsouza · 8 years ago

  After listening to this, my brain halted :P

  98

• GR

  @grinofthegrimreaper · 10 years ago

  I think there&apos;s a little misunderstanding here, the Halting problem asks if there can be ONE GENERAL algorithm that can ALWAYS decide if a program A (whatever it may be), given an input B (whatever it ma be), will terminate or not. Turing, and this demonstration, show that such an algorithm cannot exist, because there is at least ONE CASE when such a program would not give you any answer. In other words: such an algorithm cannot exist because there is one particular case that we can make up when it does not work, and that case we can make up is not a logical fallacy. <br><br>On a closing note: there are a lot of comments about Zeno&apos;s paradox. Zeno&apos;s paradox is not really a paradox, in the sense that we can solve it (not by simply observe of the phenomenon). We can logically demonstrate that an infinite sum of numbers can give you a finite answer.

  739