69 views

### The halting problem for laymen [duplicate]

This line from Wikipedia made me want to ask this question: There is, however, no general procedure for determining whether an expression involving looping instructions will halt, even when humans ...
50k views

### Why, really, is the Halting Problem so important?

I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia [article][1] correctly explains that a deterministic ...
14k 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}$ ...
10k views

### Human computing power: Can humans decide the halting problem on Turing Machines?

We know the halting problem (on Turing Machines) is undecidable for Turing Machines. Is there some research into how well the human mind can deal with this problem, possibly aided by Turing Machines ...
7k views

### Perplexed by Rice's theorem

Summary: According to Rice's theorem, everything is impossible. And yet, I do this supposedly impossible stuff all the time! Of course, Rice's theorem doesn't simply say "everything is impossible". ...
3k views

### Algorithm to solve Turing's “Halting problem‍​”

"Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist" Can I find a general algorithm to solve the halting problem for ...
4k views

### What are very short programs with unknown halting status?

This 579-bit program in the Binary Lambda Calculus has unknown halting status: ...
4k views

### Why are the total functions not enumerable?

We learned about the concept of enumerations of functions. In practice, they correspond to programming languages. In a passing remark, the professor mentioned that the class of all total functions (i....
915 views

### Is it possible to solve the halting problem if you have a constrained or a predictable input?

The halting problem cannot be solved in the general case. It is possible to come up with defined rules that restrict allowed inputs and can the halting problem be solved for that special case? For ...
949 views

### Goldbach Conjecture and Busy Beaver numbers?

Background: I am a complete layman in computer science. I was reading about Busy Beaver numbers here, and I found the following passage: Humanity may never know the value of BB(6) for certain, let ...
623 views

### To what extent is my interpretation of computable numbers correct?

Interpretation: Consider the comic strip below, where a person tries to prevent a robot from dismembering them by asking the robot to compute $\pi$ - the robot quickly produces an algorithm to ...
957 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 ...
1k views

### Halting problem without input?

I'm only a layman therefore only discuss stuff naïvely. I read some introductory articles about halting problems with a scenario that if there were such a decider accessible to us, we should be able ...