Linked Questions

7 votes
2 answers
785 views

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
3k views

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
910 views

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
183 views

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
340 views

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
170 views

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
34 views

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
20k views

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
23k views

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
11k views

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
9k views

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
5k views

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
1k views

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
2k views

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
1k views

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