Questions tagged [halting-problem]

The halting problem is a famous problem in theoretical computer science. Given as input a description of a program (typically a Turing machine) and an input to that program, the Halting problem is to decide whether that program terminates on that input.

halting-problem
Filter by
Sorted by
Tagged with
83 votes
15 answers
15k views

Infinite loops in Java

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 ...
Lion's user avatar
  • 18.8k
67 votes
13 answers
6k views

When have you come upon the halting problem in the field? [closed]

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, or when ...
Claudiu's user avatar
  • 227k
59 votes
24 answers
26k views

What exactly is the halting problem?

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" Makes ...
poundifdef's user avatar
  • 19.2k
55 votes
8 answers
21k views

Practical non-Turing-complete languages?

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 ...
Kyle Cronin's user avatar
  • 78.3k
40 votes
4 answers
8k views

Determining whether a regex is a subset of another

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 a ...
deft_code's user avatar
  • 58.2k
30 votes
1 answer
38k views

Proof that the halting problem is NP-hard? [closed]

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 given a ...
templatetypedef's user avatar
29 votes
24 answers
13k views

When is theoretical computer science useful?

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 them (...
Claudiu's user avatar
  • 227k
25 votes
9 answers
7k views

Detecting infinite loop in brainfuck program

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 out ...
Sundar R's user avatar
  • 14.4k
19 votes
2 answers
19k views

How does this proof, that the halting problem is undecidable, work?

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 accept ...
jfisk's user avatar
  • 6,185
15 votes
3 answers
2k views

Halting in non-Turing-complete languages

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 ...
Shalmanese's user avatar
  • 5,314
14 votes
8 answers
2k views

Do all regular expressions halt?

Is there any regular expression that will, for some input string, search for a match forever?
Tom Lehman's user avatar
  • 87.7k
10 votes
4 answers
3k views

"Finding all the code in a given binary is equivalent to the Halting problem." Really?

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 ...
Maxim Gershkovich's user avatar
8 votes
2 answers
547 views

Automatically and deterministicly testing a function for associativity, commutativity etc

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 ...
TheIronKnuckle's user avatar
8 votes
7 answers
4k views

Is there a "good enough" solution for the halting problem?

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 ...
EpsilonVector's user avatar
7 votes
3 answers
1k views

How can undecidable instances actually hang the compiler?

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 compilers ...
leftaroundabout's user avatar
7 votes
1 answer
211 views

Is mfix for Maybe impossible to be nontrivially total?

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 definition: ...
Dannyu NDos's user avatar
  • 2,478
7 votes
4 answers
557 views

Is finding pointers in C/C++ code statically equivalent to the Halting Ρroblem?

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 ...
Jens's user avatar
  • 8,792
6 votes
3 answers
2k views

Automated computation of algorithm time complexity for terminating algorithms

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 the ...
singpolyma's user avatar
  • 11.1k
4 votes
2 answers
1k views

Do agda programs necessarily terminate?

It has been stated a few places that all agda programs terminate. However I can construct a function like this: stall : ∀ n → ℕ stall 0 = 0 stall x = stall x The syntax highlighter doesn't seem to ...
user833970's user avatar
  • 2,749
4 votes
2 answers
933 views

Explanation of the Turing Machine Halting Problem

I'm looking for a simple explanation of the halting problem for Turing machines. I know the basis of how TMs work, how they enumerate things, machine configurations, etc., but I don't have a good ...
user2440665's user avatar
4 votes
5 answers
263 views

Java: Iterative method returning an object

Out of curiosity I came to write the following method: public Object getObject() { return this.getObject(); } Why would Java allow me to write this? This method would never return any ...
Luke Taylor's user avatar
  • 9,501
4 votes
2 answers
298 views

Is it possible to make a halting function if you don't call it on itself?

The standard proof of of the impossibility of solving the halting problem is usually something like this //does_halt() takes a function as input and returns true if it will ever finish computing ...
David Greydanus's user avatar
4 votes
1 answer
1k views

Halting really undecidable for computers with limited memory?

Turing proved that the halting problem is undecidable over Turing machines. However, real computers are not actually Turing-complete: They would be, if they had an infinite amount of memory. Given ...
user1202136's user avatar
  • 11.4k
3 votes
2 answers
4k views

Detecting if a Program is in an Infinite Loop (Read: Solving the Halting Problem)

Is detecting whether a deterministic program (i.e. state machine) is in an infinite loop equivalent to solving the halting problem? I came up with a solution, and I'm not sure why it shouldn't work: ...
user541686's user avatar
  • 207k
3 votes
3 answers
319 views

P-NP problems solved? FindBugs solves the halting prob?

There is a tool called FindBugs it can detect infinite never ending loops in a given program/ code base. This implies FindBugs can detect if a program will end or not by analyzing the code. Halting ...
cornercoder's user avatar
3 votes
2 answers
127 views

Will this algorithm terminate?

With different values in a collection, will this algorithm (pseudeocode) ever terminate? while (curElement != average(allElements)) { curElement = average(allElements); nextElement(); } Note ...
Franz's user avatar
  • 11.4k
3 votes
1 answer
294 views

poweroff redirect system halted

I'm playing with image built from Builtroot, and run with QEMU. But when I run "poweroff" command, machine not shutdown. And "System halted" appear! (See console output bellow) # poweroff # Stopping ...
manhkhoa168's user avatar
3 votes
1 answer
222 views

Does the halting p‌r‌o‌b‌l‌e‌m mean that programs cannot check other programs?

I'm taking a theoretical CS class and we just discussed the halting problem. In my understanding, the reason that the problem cannot be solved is that if there is a program Halt that tells us whether ...
Darvish Kamalia's user avatar
3 votes
1 answer
601 views

HaltingProblem in Agda?

I am working through a paper trying to implement their Haskell code in Agda. They want to formulate the halting problem by saying let bot be a program such that for any data type a: bot :: a bot = ...
user2154420's user avatar
2 votes
8 answers
3k views

Is solving the halting problem easier than people think? [duplicate]

Although the general case is undecidable, many people still do solve problems that are equivilent well enough for day to day use. In cohen's phd thesis on computer viruses, he showed how virus ...
1729's user avatar
  • 4,991
2 votes
11 answers
891 views

What would programming languages look like if every computable thing could be done in 1 second?

Inspired by this question Suppose we had a magical Turing Machine with infinite memory, and unlimited CPU power. Use your imagination as to how this might be possible, e.g. it uses some sort of ...
2 votes
1 answer
184 views

'try' can decide when a program halts

I have this function: isUndefined :: () -> Bool isUndefined x = case unsafePerformIO $ (try (return $! x) :: IO (Either SomeException ())) of Left _ -> True ...
Alon Gurny's user avatar
2 votes
2 answers
433 views

Making a function that will identify an infinite loop in existing code

I'm trying to create a function that will identify if the code in a python file will go through and infinite loop or not. This is what I have so far: def reader(filename): myfile = open(filename) ...
user3128178's user avatar
2 votes
1 answer
352 views

Does there exist an algorithm that can solve Vim Golf problems

Is it possible to create an algorithm to solve Vim-golf problems? For those not familiar with what that is, you are given two different blocks of text, and must transform the first block into the ...
Andrew's user avatar
  • 6,661
2 votes
1 answer
401 views

How is heuristic-based virus detection possible?

The Halting Problem states that it is impossible for one program to predict the output of another, or whether it will terminate. That got me thinking... how do heuristics based-scanners decide ...
Govind Parmar's user avatar
2 votes
0 answers
341 views

How to prove that "Total" is not recursive (decidable) [closed]

Halt = { f,x | f(x)↓ } is re (semi-decidable) but undecidable Total = { f | ∀x f(x)↓ } is non-re (not even semi-decidable) I need some help in proving that the Total problem is not recursive (...
Michael Anthony Leber's user avatar
1 vote
1 answer
165 views

How do I avoid non-halting functions?

I'm trying to find an algorithm on writing a high-level function - that doesn't have to halt - in Python (or Pseudo Code) that for a given list of functions [f1,...,fn] and a given list of inputs [x1,....
Kyle's user avatar
  • 154
1 vote
1 answer
5k views

How to escape infinite loop in VBA / VB.NET

bit of a stupid question, but I couldn't find any answers to it. Sadly, I made a very shameful error, where I created an endless loop by accident. Private Sub Textbox1_Change() Do While Len(Trim(...
Samuel Hulla's user avatar
  • 6,809
1 vote
1 answer
183 views

Is it possible to determine if the memory array is accessed out of bounds in a Brainfuck program?

I have written by own BF Interpreter in Assembly, and now I'm writing a BF Compiler in Java that compiles to Assembly code. I wanted to implement a little nice feature that detected if the array of ...
skiwi's user avatar
  • 68.2k
1 vote
1 answer
108 views

Why can't an infinite loop be eliminated?

The "as-if" rule is covered by these rules: The least requirements on a conforming implementation are: Access to volatile objects are evaluated strictly according to the rules of the ...
user4714342's user avatar
1 vote
1 answer
644 views

Can a program decide whether an arbitrary program halts for SOME input?

Is there a program (may-halt? p) that can tell whether there exists an input so that (p input) halts? I tried simple diagonalization, but it only tells me that (may-halt? diag-may-halt) must be true. ...
Larry's user avatar
  • 888
1 vote
2 answers
836 views

Why does the halting problem make it impossible for software to determine the time complexity of an algorithm

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()){...
Timo Willemsen's user avatar
1 vote
4 answers
3k views

Turing machine halting problem

I have a question about turing machines and halting problem. Suppose that we have Atm = {(M,w) where M is a turing machine and w is an input} and HALTtm = {(M,w) where M is a turing machine halts ...
iva123's user avatar
  • 3,475
1 vote
1 answer
156 views

Inputs to Program to Illustrate Halting Problem

Is this illustration of the haling problem correct? function halts(func) { // Insert code here that returns "true" if "func" halts and "false" otherwise. } function ...
Robin Andrews's user avatar
1 vote
1 answer
400 views

Why do we need to use the negation part in Turing's Halting Proof?

For instance, let's say I have this Turing machine, H, which tells us whether or not a program and input will halt. Let's say we call H on itself. It has to give an answer, so if it prints out "does ...
rb612's user avatar
  • 5,417
1 vote
0 answers
101 views

Every np-complete problem reduces to the Halting problem. Is this true?

I guess that every np-complete problem reduces to the np-hard problem, so the given statement is true. But don't know how to prove it.
Romil's user avatar
  • 55
1 vote
1 answer
70 views

Determining a program's execution time by its length in bits?

This is a question popped into my mind while reading the halting problem, collatz conjecture and Kolmogorov complexity. I have tried to search for something similar but I was unable to find a ...
user avatar
1 vote
0 answers
975 views

sftp large file(>1GB)failed with only specific data bytes transferred.Why?

Currently our system (Client) on AWS EC2 instance encountered a sftp problem when trying to send a large file to a customer remote sftp server (“160.xxx.xxx.35.bc.googleusercontent.com). For the small ...
hohuang's user avatar
  • 11
1 vote
1 answer
156 views

"haltingproblem" Contradiction Proof

I recently came across the halting problem contradiction proof. In the proof, we have to feed the Turing machine a copy of the program and a copy of the input to decide whether that program halts on ...
Tao Chen's user avatar
0 votes
4 answers
275 views

why there can't be a program that checks another program

I am trying to find the logical alan turing explanation why there can't be a program that checks another programs. I remember we learned in on the computation course but now i just can't find the ...
Night Walker's user avatar
  • 20.9k