tag:blogger.com,1999:blog-3722233.post612091214291991305..comments2023-09-30T21:44:03.907-05:00Comments on Computational Complexity: A result of Specker in Recursive CombinatoricsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-11803377913620087052012-02-28T06:32:34.312-06:002012-02-28T06:32:34.312-06:00I have made the correction: COL(x,y) = f(x,y) wher...I have made the correction: COL(x,y) = f(x,y) where x<y.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81093043329946832002012-02-24T17:48:19.051-06:002012-02-24T17:48:19.051-06:00Typo above, COL(min(x,y),max(x,y)) should of cours...Typo above, COL(min(x,y),max(x,y)) should of course read f(min(x,y),max(x,y)). And the references cited in the blog post do indeed use this standard definition of Ramsey's theorem.<br /><br />nnnAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11315359369209658502012-02-24T17:16:20.442-06:002012-02-24T17:16:20.442-06:00I am replying to myself here. I think the original...I am replying to myself here. I think the original proof is incorrect as Ramsey theory is ordinarily understood, where a coloring of pairs is symmetric. To fix this, define COL(x,y)=COL(min(x,y),max(x,y)) . Then given any L, all f(x_L,x_k) are identical for k>L. Hence f(x_L,x_k)=A(x_L). As each f(x_i,x_j), j>i, are identical, the result follows as in the original proof.<br /><br />nnnAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24294947672460517192012-02-24T13:20:10.561-06:002012-02-24T13:20:10.561-06:00In normal Ramsey theory I thought that the colorin...In normal Ramsey theory I thought that the coloring relation on pairs is supposed to be symmetric: COL(x,y)=COL(y,x). Your definition of coloring results in an asymmetric COL relation, however.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77323020228831334372012-02-05T16:11:21.046-06:002012-02-05T16:11:21.046-06:00I was intrigued by your suggestion that Specker...I was intrigued by your suggestion that Specker's result was the first of this type, so I posted a query on the Foundations of Mathematics mailing list to see if there were any earlier examples. <a href="http://www.cs.nyu.edu/pipermail/fom/2012-January/016163.html" rel="nofollow">Ali Enayat</a> and <a href="http://www.cs.nyu.edu/pipermail/fom/2012-January/016164.html" rel="nofollow">Andrej Bauer</a> responded that in 1952, Kleene proved the existence of an infinite recursive subtree T of the full binary tree such that T has no infinite recursive branch. Specker in fact built on Kleene's work.Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62938179910134670642012-01-31T00:10:09.542-06:002012-01-31T00:10:09.542-06:00Thanks Bill, the explanation was helpfulThanks Bill, the explanation was helpfulAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12268519875315431172012-01-30T12:56:49.591-06:002012-01-30T12:56:49.591-06:001) someone emailed me asking of I mean that A bi-i...1) someone emailed me asking of I mean that A bi-immune means that<br />neither A nor Abar has an INFINITE decidable set. YES, that is correct.<br /><br />2) Initial segment argument: Think of a set as an infinite string of 0's and 1's. We want the set A to satisfy requirements<br /><br />R_e^1: If Turing Machine M_e is total and says YES to an infinite set<br />of numbers then L(M_e) is not a subset of A.<br />(We will make some x such that M_e(x)=1 be NOT in A)<br /><br />R_e^2: similar for Abar.<br /><br />We satisfiy these requirements in the order R_1^1, R_1^2, R_2^1, R^2_1, etc...<br /><br />Initially A is the empty string (no members decided).<br /><br />Assume that A is a finite segment and you want to satsify R_e^1.<br />ASK HALT: does there exist x bigger than the segement such that<br />M_e(x) halts and says YES. If so then extend the segement that is<br />representing A to that point x (say with 0's) and make sure that x<br />itself gets a 0, so now x NOT IN A, but M_e(x) says 1.<br /><br />If the answer to the question was NO then M_e only says YES finite<br />often so the requirement is already satisfied.<br /><br />Similar for R_e^2.<br /><br />SO, A is build up segment by segment. <br /><br />that is, FIRST you decide A on (say) 1,2,3,4,5,6. <br />Then on 7,8,...,100001, etc. Each time you extend A you<br />are satisfying a requirement.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16085531734769676232012-01-30T11:05:49.555-06:002012-01-30T11:05:49.555-06:00Bill, what is an initial segment argument? (that i...Bill, what is an initial segment argument? (that is, can you sketch the proof of (1)?)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11907562399255357332012-01-30T10:40:46.683-06:002012-01-30T10:40:46.683-06:00Brilliant.Brilliant.Anonymousnoreply@blogger.com