What came to mind intuitively is what I would call C-T tests that are more or less methods of accepting some model as being a computational model or not. The question is in what amount and how could we balance the viability of the tests with problems of how effective they would be(both computationally and effective as being acceptable as testing methods) and depending on the answer would these raise circularity issues?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
Computability theory overflows with hierarchies of computability notions, which allow us precisely to compare the computational strength of diverse notions. We have the hierarchy of Turing degrees, which measures the strength of relative computability by oracles. We have the hierarchy of complexity theory and the complexity zoo, which measures the strength of diverse resource-limited computation. We have the hierarchies of the arithmetic hierarchy and that of descriptive set theory, which can measure the strength of infinitary notions of computation, and the hierarchy of the constructibility degrees, which can measure the strength of stronger notions.
All these hierarchies are quite commonly used to gauge the strength of a generalized notion of computability, whether the notion is above or below the usual Turing notion. One gains an understanding of the strength of a given computational model by fitting it into the known hierarchies and thereby also coming to know how various models of computability relate to one another.
answered Jan 27, 2022 at 17:59
-
1$\begingroup$ I don't think this is what the OP is asking about. My guess is that they are asking for some finite "test" you can perform on a putative computation system to "decide" (or make a best guess, at least) if the system is Turing-complete. $\endgroup$ Commented Jan 27, 2022 at 18:02
-
$\begingroup$ @SamHopkins Yes, my answer is that one gains such insight by fitting it into the hierarchies I mention. This is how these hierarchies are often used. $\endgroup$ Commented Jan 27, 2022 at 18:04
-
1$\begingroup$ Indeed, these hierarchies are intensely studied, and one gains much more refined information from them than just a yes/no answer as to whether the concept should count as computational. $\endgroup$ Commented Jan 27, 2022 at 18:05
-
$\begingroup$ @JoelDavidHamkins Thank you for the answer. Makes me realize that I may have been a bit naive. My intentions were more philosophically oriented. What I had in mind is something along the lines of let's say we have some model of what we deem to be a computational model. And let's say that the said model suggests that in fact many strictly c.e functions. Now if we use any means of "Church Turing testing" as I called them to see the degree of complexity as you suggested we would pretty easily see the model fails and it is fact not a model of computation. But given the density of c.e degrees... $\endgroup$– H.C ManuCommented Jan 27, 2022 at 18:32
-
1$\begingroup$ My view, in keeping with my general attitude about the relation between mathematics and philosophy, is that one should undertake the philosophical task (which is how I had understood your question) in light of the related mathematical analysis. To analyze philosophically whether a given notion should count as computational, one should first know how it fits into the known mathematical hierarchies. And further, having done this one often sees that there is a little at stake in the philosophical designation of "computational" or not--perhaps what matters is the actual computational power. $\endgroup$ Commented Jan 27, 2022 at 18:42