Yakk
• Member for 7 years, 2 months
• Last seen more than a week ago
• Canada

## 9 Answers

24 votes

A few reasons, some generic and some specific. The generic reason is that this is a long-known famous problem which many smart people have tried to solve, and many smart people have gotten wrong. ...

View answer
17 votes

You seem to be confusing the classic "self referential" based proof that the Halting problem cannot be solved with the Halting problem (aka Halt) itself. That self-referential program -- the program ...

View answer
9 votes

We have not ruled out the possibility of a simple proof that P=NP. If someone tomorrow comes up with an algorithm that solves a NP-complete problem in P time, the world changes. On the other hand, ...

View answer
Accepted answer
6 votes

The width of an image is being measured in a discrete 2 dimensional space. The image is 3840 pixels across. This means there is a horizontal band of 3840 pixels (which are each 2 dimensional regions)...

View answer
4 votes

Start off with a Finite Automaton. It has states and acceptance states and transitions. Now, give it more than one trasition rule of of each state, and say that it accepts if there exists a set of ...

View answer
3 votes

What is NP A problem is in NP if, with a polynomial-length "magically provided" proof string for any given problem instance whose answer is "yes", can verify the answer is "...

View answer
2 votes

Optimizers in C++ turn traditional C++ code into static single assignment when it can. You can think of traditional imperative programming as chaining together functional steps. struct state { int ...

View answer
1 votes

You are mistaking a map for the territory. The first thing to realize is that computers don't work on numbers. Computers work on bits and volts. We abstract that work on volts into working on bits, ...

View answer
0 votes

A formal way to approach this is to note the existence of Universal Turing Machines. Let U be a universal turing machine. Then, for any other Turning Machine T there exists a tape state T' such that ...

View answer