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
can define numbers so big, that 2n and 2n+1 is almost the same. In
any representation, whether in bits or in turing machines, if we
devide both numbers in 4 we will not necessarily get two different
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]
