On Wed, 25 Apr 2007 16:09:44 +0300 "Uri Even-Chen" <[EMAIL PROTECTED]> wrote:
> On 4/25/07, Shachar Shemesh <[EMAIL PROTECTED]> wrote: > > "Completeness" and "Consistency" relate to the relationship between the > > provability of an expression (syntax) and it's core truthfulness > > (semantics, or meaning). Since I was not talking about those, these > > hardly seem relevant. > > > > A theory cannot be either, because a theory is something that needs > > proof. In other words, using any moderately reasonable tools of proof, a > > theory can be correct and provable, correct and unprovable or incorrect > > (we usually do not let go of consistency because that leads to absurds). > > You will notice, however, that the theory is neither complete NOR > > consistent. These are measures not meant for theorems, but for logics. > > I agree. > > > Even for logics, the statement above is incorrect. Zero order logic is > > both consistent AND complete. > > I'm not sure what zero order logic is. How do you say "this sentence > is not true" in zero order logic? > > > Trivial example: Is there a number of the form "2n+1", where n is a > > whole and positive number, that divides by 4? > > You answer seems to be: Sure there is (or, at least, you cannot prove > > there isn't). There are an infinite number of such numbers. > > My answer: No, there isn't. There is, indeed, an infinite quantity of > > such numbers, but ALL of them divide by 4 with a remainder of either "1" > > or "3". > > Good example. You assume this is true for all numbers. Take any > positive number, multiply it be 2, add one, devide by 4, and you get > either 1 or 3. Although I agree with you that it's true for any > number we can represent by a real computer, I don't think it's > infinitely true. I don't think integer numbers exist to infinity. We You think wrong, it's easy do define them to infinity > can define numbers so big, that 2n and 2n+1 is almost the same. In You've got limits completely messed up. (2n+1)/2n does go to one in the limit but 2n+1 - 2n will always be 1 no matter how large the number n is > any representation, whether in bits or in turing machines, if we > devide both numbers in 4 we will not necessarily get two different Now you are talking about rounding errors and the problems of representation of floating point numbers on the computer not the results of exact arithmetic. BTW, as long as you are working with exact integers the results will always be 1 or three no matter how many bits you use (for bit represented numbers you are only interested in the bottom two in the case and you can have a zillion more that won't matter) The only thing that these mails show is some lack of understanding or knowledge of logic and what a proof actually is. You have a tendency to use points completely irrelevant to the problem to show that it is unprovable/unsolvable. Telling that the solution to the question to whether 10 is prime is dependent on what 10 is, is no proof to the question of how hard it is to compute it or whether it is computable. > results. I can't define such a specific number, since you will be > able to contradict me. It's an unknown unknown. Look what I wrote > about the largest known prime number. > > http://www.speedy.net/uri/blog/?p=25 > > > > I'm referring to the general case, whether any specific problem is not > > > in O(1). No specific problem can be proved not to be in O(1) for all > > > algorithms. > > Ok. Let's take a simple one: > > Problem: You have a list of numbers in an array. You want to either > > create a new array, or in the existing array, list the numbers in > > reverse order to the input one. > > Proof: No number in the array, with the possible exception of the middle > > element in the case of an odd sized array, is located at the right > > place. Any algorithm, by the very constraints posed by the definition of > > the problem, must be moved. Ergo: The minimal complexity for an > > algorithm that performs this operation cannot be lower than O(n). QED > > It's not a decision function. Decision functions return either 0 or > 1. I'm referring to the question whether there is any decision > function which can be proved not to be in O(the size of the input). > For example, if the input is a number represented in n bits, and the > output is a sequence of its prime factors represented in m bits, then > we are talking about m decision functions, each of them cannot be > proved not to be calculated in O(n) steps. The total result would be > calculated in O(m*n) steps, which is polynomial. But if each bit is > calculated by a different computer, in parallel, then they can all be > calculated simultaneously in O(n). If technology allows simultaneous > calculations, such as neural networks, then maybe even O(1) can be > achieved. > > Your example is simple - it can be calculated in O(n), and I just said > that there is no proof that it cannot be calculated in O(n^2) [each > bit in O(n), and for any specific input in O(1)]. Indeed, your > function is a good example of calculating each bit in O(1) (on > average). > > O(1) refers to any specific input. If you provide me with any > specific problem, and I have to return a yes/no answer (one bit), then > you can't prove that I can't return a correct answer for this specific > input in O(1). > > It can be proved by induction on the size of the input. With no input > it's obvious, and if you add one bit to the input, this problem is > considered to be "hard" (not in O(1)) if and only if it contains at > least one specific input for which it is proved to be hard. > > Uri. > > ================================================================= > To unsubscribe, send mail to [EMAIL PROTECTED] with > the word "unsubscribe" in the message body, e.g., run the command > echo unsubscribe | mail [EMAIL PROTECTED] > ================================================================= To unsubscribe, send mail to [EMAIL PROTECTED] with the word "unsubscribe" in the message body, e.g., run the command echo unsubscribe | mail [EMAIL PROTECTED]
