Linked Questions

7 votes
2 answers

Collection of real world non computable programming tasks [duplicate]

I'm quite new to computability theory and would be interested in some examples of realistic programming tasks you could encounter when working as a C++ programmer that are not computable.
Graf Aal's user avatar
0 votes
1 answer

Are the implications of the diagonalization language different from those of the halting problem? [duplicate]

Revised: In my previous question, I was confused about the implications of the diagonalization language. I concluded that it proves there are languages for which there are no recognizable turing ...
maddie's user avatar
  • 237
3 votes
2 answers

what is halting problem? [duplicate]

i have researched it on wikipedia and it produces me an unusual example and stories about Turing,so what i understand is if an program run in loop,an electronic device in cpu or in computer structure ...
Lan...'s user avatar
  • 161
0 votes
1 answer

Why is the undecidability of the Halting Problem useful? [duplicate]

My understanding: The Halting Problem is undecidable for a Turing Machine, and yet it is decidable for a linear bounded automaton (a Turing Machine with finite tape). The reason is that the only way ...
Tyler's user avatar
  • 101
0 votes
0 answers

Turing's solution to the Entscheidungsproblem [duplicate]

Based on what I have read so far, to me it sounds like Alan Turing's solution the Entscheidungsproblem means that there is no algorithmic solution to tell whether a given algorithm with input will ...
user avatar
1 vote
2 answers

Does the Halting Problem have practical relevance? I can calculate all outputs for a finite number of states and inputs [duplicate]

Coming from a digital functional hardware verification background, I don’t really understand the Halting Problem. I can represent the program as a state machine and show whether all inputs in all ...
Michael's user avatar
  • 111
0 votes
0 answers

Why it is important to understand when a particular problem is algorithmically “unsolvable.” How should I deal with this type of problems? [duplicate]

So I learned that there are some problems that cannot be solved in computer science but I want to know why is it important to understand the unsolvable algorithm and how should I deal with it.
Randompple's user avatar
146 votes
3 answers

How can it be decidable whether $\pi$ has some sequence of digits?

We were given the following exercise. Let $\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$ ...
Raphael's user avatar
  • 72.5k
59 votes
13 answers

Is C actually Turing-complete?

I was trying to explain to someone that C is Turing-complete, and realized that I don't actually know if it is, indeed, technically Turing-complete. (C as in the abstract semantics, not as in an ...
TLW's user avatar
  • 1,414
36 votes
8 answers

What are the simplest examples of programs that we do not know whether they terminate?

The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. ...
MaiaVictor's user avatar
  • 4,137
32 votes
5 answers

Proof that dead code cannot be detected by compilers

I'm planning to teach a winter course on a varying number of topics, one of which is going to be compilers. Now, I came across this problem while thinking of assignments to give throughout the quarter,...
thomas's user avatar
  • 421
9 votes
1 answer

Why can't we solve the Halting Problem by using Artificial Intelligence? [duplicate]

Yesterday I was reading about Computability and they mention the Halting Problem. It got stuck in mind all day until I remember that some weeks ago, when learning Java, the IDE (Netbeans) show me a ...
nmomn's user avatar
  • 377
20 votes
1 answer

Do fully optimizing compilers for terminating programs exist?

In Andrew W. Appel's book, Modern Compiler Implementation in ML, he says under chapter 17 that Computability theory shows that it will always be possible to invent new optimizing transformations and ...
sshine's user avatar
  • 519
13 votes
2 answers

Are there any existing problems that wouldn't be solvable with a halting oracle?

I understand that most problems are trivial if a halting oracle is available (or, I think equivalently, hyper-computation). However, applying the argument that shows the Halting Problem is impossible ...
ike's user avatar
  • 235
9 votes
3 answers

Halting problem - one issue that's bothering me

To my knowledge, halting problem asks if there exists a program that decides whether a program being tested, given some input data (no matter what program it is, or what input data we give) will ...
user4205580's user avatar

15 30 50 per page