It is known that the halting problem cannot have a definite solution, one that a) returns true <==> the program does indeed halt, and b) handles any input, but I was wondering if there are good ...

Whenever people ask about the halting problem as it pertains to programming, people respond with "If you just add one loop, you've got the halting program and therefore you can't automate task" Ma...

Since Nothing >>= f = Nothing for every f, the following trivial definition is suitable for mfix: mfix _ = Nothing But this has no practical use, so we have the following nontotal definiti...

By the time I first read serious criticism on -XUndecidableInstances, I had already completely accustomed to it, seeing it as merely removal of an annoying restriction Haskell98 has to make compile...

In class, we learned about the halting problem, Turing machines, reductions, etc. A lot of classmates are saying these are all abstract and useless concepts, and there's no real point in knowing th...

I've read some articles about big-Oh calculation and the halting problem. Obviously it's not possible for ALL algoritms to say if they ever are going to stop, for example: while(System.in.readline...

I have written a simple brainfuck interpreter in MATLAB script language. It is fed random bf programs to execute (as part of a genetic algorithm project). The problem I face is, the program turns o...

Was just reading the highly voted question regarding Emulators and the statement It's been proven that finding all the code in a given binary is equivalent to the Halting problem. Really st...

I'm not too deeply rooted in the very formal side of static code analysis, hence this question. A couple of years ago I read that distinguishing code from data using static code analysis is equiva...

I'm going over the proof for The Halting Problem in Intro to the Theory of Computation by Sipser and my main concern is about the proof below: If TM M doesn't know when it's looping (it can't acc...

I have a large collection of regular expression that when matched call a particular http handler. Some of the older regex's are unreachable (e.g. a.c* ⊃ abc*) and I'd like to prune them. Is there ...

There are a lot of related questions here on SO, but they all ask about writing a program to compute the complexity of arbitrary algorithms (which is obviously undecideable). I am willing to make t...

When have you ever personally come upon the halting problem in the field? This can be when a co-worker / boss suggested a solution which would violate the fundamental limits of computation, o...

Is it possible to construct a higher order function isAssociative that takes another function of two arguments and determines whether that function is associative? Similar question but for other p...

Look at the following infinite while loop in Java. It causes a compile-time error for the statement below it. while(true) { System.out.println("inside while"); } System.out.println("while termin...

Nearly all programming languages used are Turing Complete, and while this affords the language to represent any computable algorithm, it also comes with its own set of problems. Seeing as all the a...

In this answer to a question about the definitions of NP, NP-hard, and NP-complete, Jason makes the claim that The halting problem is the classic NP-hard problem. This is the problem that gi...

Is there any regular expression that will, for some input string, search for a match forever?

The halting problem cannot be solved for Turing complete languages and it can be solved trivially for some non-TC languages like regexes where it always halts. I was wondering if there are any la...