Is effective solvability a coherent and/or useful concept? [closed]

Question

I am aware of Turing's proof of the undecidability of the halting problem (and I think I understand it). What I'm asking is quite different. I shall define what I mean by "effectively solvable":

A problem $P$ is effectively solvable if there exists an agent $A_P$, such that for any specific instance of $P \, (P_i)$, $A$ can solve that instance of the problem $(P_i)$ in a finite time.

 
Imagine $A_P$ as a superintelligence with unbounded (but finite) computational power, and unbounded (but finite) memory. $P$ is effectively solvable if $A_P$ would eventually (in finite time) produce a correct solution for any given instance of $P$.
 
It may be the case that there does not exist any algorithm that "solves" a certain class of problems say sigma $*$ problems (suppose that sigma problems are a certain kind of mathematical problem). However, this does not mean the problem is not effectively solvable. For any given sigma problem, a sufficiently intelligent agent (or sufficiently competent mathematician) may be able to eventually find its solution(s) (or determine that no such solutions exist) using an (unbounded) number of mathematical tricks. The mathematical methods applied to sigma problems is limited only by the creativity of the agent concerned. There are essentially an infinite number of strategies, from which a finite subset may be drawn from in sequence (forming an algorithm) to apply to a particular sigma problem.
 
Effective solvability (or effective decidability) is different from the traditional notion of decidability in that problem that are effectively solvable do not require a finite number of steps which always guarantee a solution. In fact, for each instance of an effectively solvable problem, a different algorithm may be used. There may be no general algorithm that solves all instances of a problem, but for each instance of the problem, a tailor made algorithm may exist.
 
Going entirely off my intuition here, I think the following is a definition of "effectively solvable":

A problem $P$ is effectively solvable for $A_P$ if $\not\exists$ an instance $P_i$ of $P | A_P$ does not solve $P_i$ in finite sequence of steps.

OR:

A problem $P$ is effectively solvable if $\forall$ instances $P_i$ of $P$, $A_P$ can correctly solve $P_i$ in finite time.

 
If there is a tailor made algorithm for every instance $P_i$ of a problem $P$, then a sufficiently intelligent agent can in practice solve every instance of the problem (by searching solution space for said algorithm when confronted with that instance of the problem). Thus even if in theory no general solution to the problem exists, in practice, specific solutions to each $P_i$ always exist (provided the above criteria is satisfied).
 
While some of such problems may be "undecidable", they are in actuality (for all practical purposes) "effectively solvable".
 
The set of effectively solvable problems is a superset (and I believe that it is a proper superset) of the set of decidable problems.
 
 
I do not know whether the halting problem is effectively solvable (I'm starting to believe that it's not). That's not my major interest though (I am curious to the answer) What I am truly interested in is effective solvability.
 
I am interested in effective solvability, because the range of problems that can be solved by an AI is not (necessarily) the range of problems that can be solved by a Turing machine, but the range of problems that are effectively solvable. I feel that the traditional (Turing) notion of decidability is insufficient when the computer is a sufficiently (pun intended) intelligent agent. Thus when we ask the question:
"What problems can a computer solve?"
I feel the set of effectively solvable problems and not (necessarily) the set of decidable problems is the answer.
 

What are some problems that are not effectively solvable by your definition?

I do not know of any, and I suspected there may be none. To hazard a guess however:

1. Problems which may involve randomness may not be effectively solvable. In particular if the computer gets the right answer, but doesn't know it got the right answer, then it can never solve that instance of the problem. Such problems are thus not effectively solvable.
    
   As a concrete example of such a problem, imagine a machine delta. Delta is non deterministic. Delta (uses its input) to randomly select/construct an arbitrary Turing machine $M$. Delta halts if $M$ halts, and delta runs forever if $M$ runs forever. Does delta halt in a particular input is not effectively solvable.
2. Any problem for which there exists a single instance of the problem for which there does not exist in algorithm that always produces the correct answer for that instance of the problem are not effectively solvable.
    
   In general, non deterministic problems may be not effectively solvable.

 
Let the sufficiently intelligent agent be Omega. For the problem that Omega is tasked to solve, Omega can solve instances of that problem even if Omega does not have a general algorithm for all instances of the problem. Omega can craft a tailor-made solution (algorithm) to any specific instance of a problem. Let all tailor-made algorithms (TMAs) Omega uses on instances of any problem use steps that come from a (countably) infinite set $S$. Consider the set of all finite sequences of steps from $S$, let's call this $T$. $T$ is the set of all possible TMAs that Omega can use on any instance of $S$. $T$ can be thought of as the "toolkit" of Omega. When Omega encounters a particular instance of a particular problem (for which Omega has no general algorithm to solve), Omega crafts a TMA to solve that particular instance. This crafting can be thought of as Omega selecting a TMA from $T$.

$T$ is countably infinite. Thus Omega's actual operation is selecting an algorithm from an infinite set of algorithms whenever faced with a particular instance of a problem. However, Omega has only finite memory. Thus, Omega never actually stores $T$ in memory. What happens is that whenever Omega faces a certain $P_i$, Omega tries an algorithm to solve that $P_i$. This algorithm may be generated on the spot. However, if Omega faced an infinite number of $P_i$s for some $P$, then it could be seen how Omega employs an infinite number of TMAs to solve each instance of $P$.

It may very well be the case (and it probably is), that Omega selects TMAs from a subset (finite or infinite. The set of TMAs I can draw from in attempting a solution is infinite, but most of that set would contain ineffective algorithms, and I don't actually consider them. The set of TMAs I draw from is most likely finite, though as it is a function of my knowledge, experiences etc, it may be unbounded).
  As Omega increases in intelligence, the set of TMAs it can draw from becomes increasingly larger (as meaningful as this concept is when the two sets (if both are infinite) have the same cardinality). Higher intelligence gives Omega a larger toolkit.
 
When we say Omega can effectively solve $P$, we're saying that if Omega was fed sequences of some $P_i$ endlessly, that there would never come a $P_i$, for which Omega would fail to solve $P_i$ in a finite time. It is this sense in which we consider Omega hypothetically attempting all $P_i$, in which it becomes useful to think of Omega has having an infinite set of algorithms from which it can draw from.
 
Omega is not a hyper computer or Turing oracle, and may be safely thought of as a Turing machine (or equivalent model of computation). Omega is only faced with specific instances of a problem, and does not need to have a general solution of the problem to be considered as effectively solving it.
 
Assume Omega can effectively solve $P$, but does not know a general algorithm to solve $P$. If for each $P_i$, Omega adopts $t_i$, then you could construct a method for solving $P$ as follows:

If $P_i$, then do $t_i$.

 
However, if the sets of all instances of $P$ is an infinite set, then the above method would also contain an infinite number of steps. Does, the above method is not an algorithm.
 
Yet, it may be the case that Omega does not have a general algorithm for solving $P$, but there does not exist some $P_i$, which Omega would not solve in finite time.
 
Effective solvability can be seen as asking if there is an infinite sequence of steps that solve the problem in the general case. Thus, if a problem is effectively solvable, there may be no algorithm that solves that problem (as such an algorithm would need an infinite number of steps). It is because effective solvability permits methods which contain an infinite number of steps, that I assert that the space of effectively solvable problems is a superset of the space of Turing decidable problems. It is why I draw the distinction between effective solvability and Turing decidability.
 
The way I think of Omega employs the concept of Vingean uncertainty. The more intelligent Omega is, the more confident I am that Omega would reliably achieve its goals (in this case solve specific instances of specific problems) and the less knowledge I possess of the particular steps Omega would take in achieving it's goals.
 
Omega is of arbitrarily high intelligence. If I am to ask the question of "What problems can Omega solve?", then the space of all effectively solvable problems seems like the correct answer to me (I am very convinced that the space of Turing decidable problems may be a wrong answer).

---

 
 

Tl;Dr

Let's say we have a super intelligent AI of arbitrarily high intelligence with unbounded (but finite) processing power and unbounded (but finite) memory called Omega. Omega is implemented on a Turing machine (or other equivalent model of computation). When Omega is faced with an instance $P_i$ of a problem $P$, being sufficiently intelligent, (unless that instance of the problem is unsolvable)Omega can craft a Tailor Made Algorithm (TMA) $t_i$ to solve said $P_i$. It may be the case that there does not exist a $P_i$, which if faced with, Omega would not successfully craft a $t_i$ to solve it in unbounded (but finite) time. In this case, while Omega cannot decide $P$, we say that Omega can effectively solve $P$.
 
If Omega can effectively solve $P$, then an algorithm to solve $P$ in the general case can be crafted as follows:

If $P_i$ then do $t_i$.

However, if the set of instances of $P_i$ is infinite, then the algorithm described above is infinite. Thus, even if Omega does not have an algorithm to solve the decision problem in the general case, it can effectively solve that problem.
 
This relies on there being no instances of the problem that are themselves not decidable. If for all instances of the problem it is decidable, then it might be effectively solvable. I used "of arbitrarily high intelligence because if an agent is sufficiently intelligent, then giving them unbounded (but finite) processing power, unbounded (but finite) memory, and unbounded (but finite) time would let the agent solve that instance of the problem.

---

 
 

Questions

Does a concept of effective solvability already exist?

Is effective solvability a coherent concept?

Is it a useful concept?

 
Please point me in the right direction to do further study on effective solvability.

Answer 1

By your definition, all problems with defined finite solutions are effectively solvable. Just set the algorithm $A(P_i)$ to be "output $x$", where $x$ is the solution to $P_i$. For example, the algorithm you would use to solve the instance of IS_PRIME on 37 is "output yes."

Now the algorithm picking algorithms to apply is uncomputable, but you said you didn't care about that.

Answer 2

I don't totally understand the question, but I think that the answer is this:

Theorem: Let $\{A_i\}$ be a sequence of Turing Machines such that $A_i$ computes $f(i)$ on an empty input. Then there exists a single Turing Machine $T_f(x)$ that computes $f$.

You also have the ability to build Turing machines that interlace, like so:

1. Run $A_1$ for one step
2. Run $A_1$ for two more steps
3. Run $A_2$ for two steps
4. Run $A_1$ for three more steps
5. Run $A_2$ for three more steps
6. Run $A_3$ for three steps

...

Stop when $A_x$ finishes and return what it returned.

---

I think that you misunderstand the meaning of the word computable. If you can deterministically solve a problem with pencil and paper, then that problem is computable. The definitions happens to encapsulate what a computer can do, but that's not where it came from. In particular, nothing in the following quote is correct

I am interested in effective solvability, because the range of problems that can be solved by an AI is not (necessarily) the range of problems that can be solved by a Turing machine, but the range of problems that are effectively solvable. I feel that the traditional notion of decidability is outdated when the computer is a sufficiently intelligent agent (one may make the argument that machine learning already renders traditional decidability obsolete as far as this problem is concerned

It is conceivable that the computable functions are not exactly the same as the function that can be actually calculated by a physical computer, but that has nothing to do with AI or Machine Learning. Those things do not increase the realm of things solvable by a computer.

Answer 3

A problem $P$ is effectively solvable if there exists an agent $A_P$, such that for any specific instance of $P$ ($P_i$), $A$ can solve that instance of the problem ($P_i$) in a finite time.

This definition hinges entirely on what you define an "agent" to be. If $A_P$ is a Turing machine, then your definition is identical to the usual notion of decidability. An infinite (countable) computable sequence of Turing machines cannot decide anything that a single Turing machine can't decide.

Alternatively, you could define $A_P$ to be some kind of oracle that can magically choose the appropriate algorithm. But you have to specify what kind of oracle it is, so as not to trivialize the definition. (For instance, as others have already pointed out, any instance of any problem can be "solved" by the trivial algorithm that simply prints the correct answer.) And you seem to be interested in a class that corresponds to real, implementable machines, which rules out oracles.

Answer 4

Your notion of effectiveness implies a physical (material) criterion of verification. Keep in mind that computational models, albeit $-$ to some extent $-$ materially realizable, are nonetheless essentially mathematical in nature. In other words, they try to be ahistorical.

An example might help clarify the issue. We know the solution to the Busy Beaver problem up to 4 states. Generic approaches (which included computer algorithms) have helped those who attempted to solve the problem in this limited version, by greatly reducing the problem space, but in the end they had to rely on their ability to analyse every single remaining Turing machine, to see how it behaves. In that effort, they had to treat them as singular problems, not anymore as members of a problem set.

So, what you see is that, from a (meta)mathematical point of view, this problem that we still view as a set, is in fact grouped only by its definition, but cannot be associated to a single formalized strategy of resolution. This means that the identity of the hipothetical agent that solves all instances of the problem can only be given historically, and your attempt at giving an abstract characterization of it is inevitably aporetic (meaning that it leads nowhere).