patternMinor
Are there problem instances which we know to be unsolvable?
Viewed 0 times
problemknowinstancesareunsolvablewhichthere
Problem
As it says in the title:
Are there problem instances which we know to be unsolvable?
Or equivalently
Are there any promise problems with a finite number of possible inputs
which are undecidable?
Please note:
I realize that many computational problems are known to be unsolvable, but to the best of my knowledge (limited it may be) all must take an infinite number of inputs. Therefore, their existence does not imply that there cannot be an infinite number of algorithms each solving a subset of these problems.
Remark: I only wish to consider well-defined problems, i.e. every input has a correct output.
On a related note, is there a complexity hierarchy for promise problems with only a finite number of possible inputs?
Are there problem instances which we know to be unsolvable?
Or equivalently
Are there any promise problems with a finite number of possible inputs
which are undecidable?
Please note:
I realize that many computational problems are known to be unsolvable, but to the best of my knowledge (limited it may be) all must take an infinite number of inputs. Therefore, their existence does not imply that there cannot be an infinite number of algorithms each solving a subset of these problems.
Remark: I only wish to consider well-defined problems, i.e. every input has a correct output.
On a related note, is there a complexity hierarchy for promise problems with only a finite number of possible inputs?
Solution
Every problem with a finite number of inputs is computable.
Proof: Suppose that the inputs are $i_1,\ldots,i_n$ and that the desired outputs are $o_1,\ldots,o_n$. Then the following program solves the problem:
Proof: Suppose that the inputs are $i_1,\ldots,i_n$ and that the desired outputs are $o_1,\ldots,o_n$. Then the following program solves the problem:
- If the input is $i_1$, output $o_1$.
- If the input is $i_2$, output $o_2$.
- ...
- If the input is $i_{n-1}$, output $o_{n-1}$.
- Output $o_n$.
Context
StackExchange Computer Science Q#85775, answer score: 6
Revisions (0)
No revisions yet.