If FLT had really been solved then I would know that. (Note- I am not bragging about how much math I knew; I am bragging about how much math I knew of.)Is that a rigorous proof technique? No, but it is useful and often correct.
(All of the math that I refer to below is done rigorously in my writeup here.) As a Grad student I noticed the following:
- Let C(x) be the length of the shortest description of x (the usual Kolmogorov complexity).
- It is easy to show that C ≤T HALT.
- The only proof I had seen that C was not computable was by contradiction: assume C is computable and then use that to create a string x that had no short description along with a short description of x. This proof did not use HALT at all! It was the only proof I knew of that a set was undecidable that did not use HALT (are there others?)
- Hence, from what I knew, it was possible that C was of intermediary Turing degree- neither decidable nor Turing-complete. This would be a natural intermediary Turing degree!! (As opposed to sets that are constructed for the sole purpose of being of intermediary Turing degree.)
If there was a natural intermediary Turing degree then I would know that. (Note- I am not bragging about how much computability theory I knew; I am bragging about how much computability theory I knew of.)Was my intuition correct? Unfortunately yes- one can show that HALT ≤T C. Too bad- I would have preferred to be wrong and have seen a natural intermediary Turing degree. (The writeup I pointed to above has the classic proof that C is undecidable, the proof that C ≤T HALT and the proof that HALT ≤T C. The proof of the latter I got from Peter Gacs.) (NOTE- I had it as Gac but a commenter pointed out that it is Gacs.)
There might be a typo when you wrote C_s instead of C_{s_0} in line 2 of the proof of Theorem 5.2. Or maybe you meant that statement to start "Find s_0 such that for all s >= s_0, ..."
ReplyDeleteYES, THANKS!
ReplyDeleteI have fixed it.
GASARCH
On one of those PBS "GED" shows I saw them "prove" that pi was equal to exactly 22/7. On that day I lost respect for PBS and began to question the lessons taught by Bert and Ernie as well.
ReplyDelete"It was the only proof I knew of that a set was undecidable that did not use HALT (are there others?) "
ReplyDeleteYes, there is a trivial example. Let S be the set defined by saying n is in S iff n is not in the nth decidable set. Then S is non-decidable by the usual diagonalization argument.
Xamuel. Thanks!
ReplyDeleteLets call your set X.
Now the question arise: is X equivalent
to HALT? I suspect either YES or
it may depend on the actual programming system you are using. I suspect that for any ``natural'' programming system
(not sure how to define that) the answer is yes.
GASARCH
My apologies from Peter Gac, if he exists, but maybe you wanted to write Gacs.
ReplyDelete"Lets call your set X.
ReplyDeleteNow the question arise: is X equivalent
to HALT? I suspect either YES or
it may depend on the actual programming system you are using. I suspect that for any ``natural'' programming system
(not sure how to define that) the answer is yes."
One way to make the set more precise is to clarify that when we say a set T is "decidable", we mean there exists a total computable function f such that f(n)=1 iff n is in T.
And then, define X to be the set such that n is in X iff f(n)!=1 (or f(n) doesn't halt), where f is the nth (not-necessarily-complete) computable function, which you can determine however you like, e.g., the function whose C code's binary representation is n. (The smarty-farty keyword to use here is "Godel number")
In that case, X is equivalent to HALT. Given HALT, deciding X is easy. Conversely, to determine whether a TM M halts, let M' be the machine which runs M and then, if that ever finishes, outputs 1. Then M halts iff M' ouputs 1 iff n is outside X where n is the number of the function computed by M'.
Xamuel- Great, thanks again.
ReplyDeleteI have heard that in recursion theory
sets TEND to be Turing-complete
unless you MAKE THEM not Turing-complete. Your example is an...
example of this.
Faculty position at Duke: http://www.cs.duke.edu/department/resources/openings.php
ReplyDeleteAd lists "Algorithms" and "Computational Economics" as areas of interest.
Faculty position at UPenn in "Market and Social Systems Engineering": http://jobs.acm.org/c/job.cfm?site_id=1603&jb=7249905
ReplyDelete"focused on topics at the burgeoning intersection of systems engineering, operations research, game theory and mechanism design, algorithmic aspects of economics and sociology, and many related areas. "
Anonymous posts: "Faculty position at UPenn in "Market and Social Systems Engineering"
ReplyDeleteGASARCH's post seemed to me to be a "Great Truth" post, in the sense that the opposite assertion is also a great truth. To see this, let's split GASARCH's heuristic in two:
--------------------
The Principle of Proof Conservatism: "If that proof was right, I would have known about it."
--------------------
The Principle of Axiom Activism: "If those postulates were wrong, I wouldn't have known about it."
--------------------
As a concrete example, let's recall a few historical reasons why the applicant for the above faculty position should embrace "Axiom Activism" (which might also be called "Postulate Progressivism"):
--------------------
Non-euclidean geometry: "If Euclid's parallel postulate were disposable, then I would know that."
--------------------
Control theory: "If control (rather than efficient flapping) were the key to powered flight, then I would know that."
--------------------
Computer science: "If machines (rather than human computers) were the key to numerical computation, then I would know that."
--------------------
Genomics: "If robots (not lab technicians) were key to genomic experiments, then I would know that."
--------------------
Enterprise: "If reliable and efficient simulation algorithms were the key to initiating large-scale enterprises, then I would know that."
--------------------
As Yogi Berra, Niels Bohr, Casey Stengel, Dan Quayle, Mark Twain, Will Rogers, Winston Churchill, Albert Einstein, G. B. Shaw, Disraeli, Confucius, and Freeman Dyson (and many more) all are reputed to have said: "Predictions are hard, especially about the future" ... yet nonetheless I will suggest that the following progressive postulates are likely to emerge in the 21st century:
--------------------
Progressive Complexity Theory : "P and NP are not the most natural classes for studying computational complexity."
--------------------
Progressive QIT: "Coherent flows are not the most natural instantiations of classical and quantum dynamical processes."
--------------------
In short, the history of the STEM enterprise in the 19th and 20th centuries suggests that GASARCH's heuristic can reasonably be generalized and broadened to a principle that has been respected throughout history by great mathematicians, scientists, engineers, and enterprises: "Respect theorems, but not postulates."