TE
TechEcho
Home24h TopNewestBestAskShowJobs
GitHubTwitter
Home

TechEcho

A tech news platform built with Next.js, providing global tech news and discussions.

GitHubTwitter

Home

HomeNewestBestAskShowJobs

Resources

HackerNews APIOriginal HackerNewsNext.js

© 2025 TechEcho. All rights reserved.

Am open to constructive criticism: My Halting Problem solution

3 pointsby vitarnixofntrntabout 1 year ago
I may be wrong about this, feel free to offer constructive criticism:<p>Step 1: Load the program and initialize my Halting Problem program&#x27;s variable n to 0.<p>Step 2: Save the register context (meaning all the values in all the registers in a CPU) to memory location A.<p>Step 3: Step variable n + 1 instructions.<p>Step 4: Save the register context (meaning all the values in all the registers in a CPU) to memory location B.<p>Step 5: Compare the contents of memory location A to memory location B. If they match exactly, then exit with a return code of &quot;This program is in an infinite loop&quot;, if they don&#x27;t match exactly, then goto Step 2.<p>The variable n is an unsigned fixed point arbitrary precision integer.<p>If this solves the Halting Problem as proposed by Alan Turing, then does this also solve P versus NP?<p>An example of this working:<p>ax is a 2 bit register initialized to 0.<p>100: add 1 ax<p>101: jmp 100<p>ax is 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3<p>0 is compared to 1, 1 is compared to 3, 3 is compared to 2, 2 is is compared to 2, wait, that&#x27;s an infinite loop...<p>Well, my program basically detects if a infinite loop is of 1 iteration or two iterations or three iterations or ... iterations, but only infinite loops and not finite loops and in a finite amount of time. This means that finite loops don&#x27;t trigger my program ever, only infinite ones after a finite amount of time.<p>TLDR: A turing machine can run my program and determine whether any other program halts or infinite loops in a finite amount of time, never infinite only if the variable n can be infinitely large.

4 comments

salawatabout 1 year ago
Halting Problem isn&#x27;t &quot;does this one instance of a program return&quot;. Halting problem is with a Turing Machine, implement an algorithm that will determine whether any arbitrary turing machine from the space of all possible Turing machines return.<p>You cannot generally decide the problem, because at best your algorithm can only practically determine &quot;the Turing Machine under test has not returned...yet. The Turing Machine capable of ultimately deciding the returnability of TMuT, would necessarilly have practically infinite runtime.<p>And for that matter, bring yourself out of TM&#x27;s and you&#x27;ve got all sorts of other nasty constraints that make the Halting Problem Solver unimplementable in the real. What happens when brownouts happen? Single-event-upsets? Rowhammer events? You couldn&#x27;t win in the purely abstract theoretical, so even trying to get a literal win in the real doesn&#x27;t stand a chance.<p>Halting Problem is Computer Science&#x27;s realization that there is always a bigger Turing Machine, much like how mathematicians understand there to be infinitely many primes. Within the constraints of the axiomatic model of computation; you cannot put a pin in the entire space. Only increasingly large swathes of the space at the cost of completely unreasonable respurce expenditure.<p>Or as I like to think of it, HP is the understanding that only 2 people ever understood this code in it&#x27;s totality. God, and me when I was writing it. And I long ago ditched that original context that allowed me to claim I understood it.
评论 #39773127 未加载
auroralimonabout 1 year ago
Consider: are all programs that don’t halt infinite loops?<p>Perhaps one which experiences exponential growth in some variable.
评论 #39772717 未加载
评论 #39773122 未加载
评论 #39772720 未加载
Kluggyabout 1 year ago
As people said, a turning machine has infinite memory and program space. Just checking for context and program position doesn’t solve all cases of never halting.<p>Take for example a program that attempts to calculate the <a href="https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Collatz_conjecture" rel="nofollow">https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Collatz_conjecture</a><p>Some inputs would rapidly get answered. Most won’t. If you can prove it’s halt-able for all inputs, you’ve won a Nobel and will be well off for life.<p>Good luck.
评论 #39773771 未加载
评论 #39773727 未加载
ubermanabout 1 year ago
while true i += 1
评论 #39772617 未加载