The "Web of Wars" shows a magnitude 7 conflict between Australia and Thailand, and nothing between Australia and Vietnam. Similarly, there is nothing between the US and Vietnam.
I think the authors have assigned links due to the Vietnam war to Thailand.
>If a person could find an function f(x) that returns the xth prime number, [blah blah]
Actually, you can. Anyone proficient in a programming language can code one easily enough, and anyone with any math experience can write out a description of said function. I think you meant a "simple" function f(x) (i.e., non-recursive), which I think has been proven impossible (although don't take my word for it).
There are simple functions f(x), for appropriate definitions of "simple". Here is one.
Define the constant A by:
A = \sum_1^\Infty (p_n / 10^(t_n))
where \sum denotes summation, p_n is the n-th prime, and t_n is the n-th triangular number. Then A = 0.2030050011... In particular, A is a constant, and so "simple". Now define the function
f(n) = floor(10^(T_n) * A)
where floor is the integer part truncation of the argument, and T_n is the sum of the first n triangular numbers:
T_n = 1 + 3 + 6 +... + t_n
Then, up to bone-headed off-by-one type errors on my part, f(n) = p_n.
You may or may not regard this function as "simple". It is almost certainly not useful for generating primes.
It is not hard to show that no non-constant polynomial can take on only prime values as inputs range over the integers. Rather more interestingly, there are (multi-variate) polynomials whose positive values are exactly the primes, but who also take on a bunch of "junk" negative values.
Cheers, quokka.
Re:Some interesting implications
on
Share The Pi!
·
· Score: 1
Do you have a constructive proof of this oracles existence? Constructive is the key word here. The problem is similar to finding the (Kolmogorov) complexity of a natural number. You can prove that every number does have a complexity (measured as the minimum size representation of that number), but you can't compute the complexities. The function exists, but you can't compute it.
I did not make myself clear. I don't claim that I can computable construct the Halting Problem oracle. I just point out that such an oracle exists.
Indeed, this is the whole point of using an oracle: it allows the Turing machine to access information that it could not possibly compute for itself. If we restricted oracles to effectivley computable sets then we may as well not use them at all: just replace the oracle with a subroutine that computes the oracle set itself.
It is a mistake to conflate Computability Theory (also called Recursion Theory) and Complexity Theory. The latter is the more important to CS, and involves the analysis of algoriths for efficiency. The former is more abstract (as the use of uncomputable oracles suggests) and concerns itself with questions of the existence (or otherwise) of algorithms, but not their efficiency.
[Me] Randomness is not an essential part of the study of Turing machines-with-oracle, and the Halting Problem does not involve randomness at all.
[Laplace] Not at all? The fields share many similarities, and it's hard to find a modern discussion of one without the other.
In general, this sentence is not true. I have had very little exposure to the theory of randomness, so I can't make any useful claims about the similarity of it to Computability theory.
However, the Halting Problem, as a pioneering result in Computability theory, is quite independent of randomness. Computability Theory is not the same as Complexity Theory (in which statistics plays an essential roles), and it has a large literature which doesn't mention randomness at all.
Cheers,
quokka
Re:Some interesting implications
on
Share The Pi!
·
· Score: 1
Um, stupid comment. The Halting Problem is a problem because you can't show that every turing machine program halts (or doesn't halt). Are you really interested in the modern research in this field?
The comment to which you are responding isn't stupid at all. With a suitable oracle, a Turing machine can indeed solve the Halting problem.
Indeed, let K be the set of all (Goedel numbers) of (oracle-less) Turing machines which halt when started with empty input. Then a Turing machine with a K-oracle can trivially solve the Halting Problem: it just examines its input (which will be the Goedel number of a Turing machine) and checks if it lies in K. If so, it answers "yes" and otherwise answers "no".
Turing's theorem is much more interesting that you seem to give it credit for. Let B be a set of natural numbers. Define the "B-Halting Problem" as
Given an arbitrary Turing machine, determine whether that Turing machine, when equipped with a B-oracle, halts after being started with empty input.
Then Turing's proof shows that no Turing machine equipped with only a B-oracle can solve the B-Halting Problem. The usual, oracle-less, version is a special case of this: just take B = empty set.
Randomness is not an essential part of the study of Turing machines-with-oracle, and the Halting Problem does not involve randomness at all.
Cheers,
quokka
Turing machines with oracles
on
Share The Pi!
·
· Score: 1
Oracles are fundamental to the mathematical field of
Recursion Theory (which is also called Computability Theory.) The concept of a Turing
machine equipped with an oracle allows us to give
a definition of the "computational information
content" of a set of natural numbers.
A (rough) definition goes as follows.
Suppose B is a subset of the natural numbers
N = {0, 1, 2, 3,...}. Then a B-oracle is a device
which can correctly answer any question of the form
"is x an element of B?", where x is a natural
number. By "answer" we mean that given a
natural number x, the oracle will in finite
time answer "yes" or "no", depending on whether
or not x is actually in B.
For some sets (such as the set of primes)
we can build
an oracle easily: just write a computer program
to do it. For the primes the program could
look something like this. The number, x, is
given:
If x = 1, answer "NO" and stop.
Set d = 2.
If d * d > x, answer "YES" and stop.
If d divides x, answer "NO" and stop.
Increment d by one.
Goto step 3
We don't care that this algorithm is horrifically
inefficient: we are just interested in the
fact that there is an algorithm to recognize
the primes.
For most sets though, we can't write a progrem to do
this: under the generally accepted notion of "computability" (which comes from Church's Thesis) only countably many subsets of N are
computable in this way, while N has uncountably
many subsets. In these uncomputable cases, an
oracle is assumed to exist as if "by magic."
Now, suppose M is a Turing machine equipped
with a B-oracle. This machine is just like
an ordinary Turing machine, except it can ask
its oracle any question of the form "is x an
element of B?".
[One way to imagine M is to assume
it has a second, write-only infinte tape, on
which is written an infinite string of zeros and
ones. The n-th digit is one exactly if n is an
element of B. Then, to "consult the oracle", M
just reads the appropriate digit on its second
tape. Any specific digit on this tape can be
reached in a finite number of steps ("finite time"), so the second tape, along with some
read logic in the machine itself, acts as the
oracle.]
Further suppose that M "recognizes" the set A,
which is itself a subset of the naturals. That is,
suppose that M acts as an A-oracle, able
to correctly answer any question of the form
"is x in A?". In this case we say:
A is Turing computable relative to B
This relationship is written A <=_T B (where the
underscore represents a subscript, and the ugly '<=' is meant to represent the "less than
or equal" sign.)
If A <=_T B and B <=_T A then
we write A =_T B and say that A and B are
Turing equivalent. From the stand point
of computation, A and B are essentially the same.
However, the real interest lies in the relation <=_T itself. This relation turns out to
give an extremely rich structure to the subsets
of the natural numbers, and is the subject of
much mathematical research.
The modern standard reference for this field
is Soare. This is targetted at graduate
students and upper-level undergraduates. Other
good references are Rogers (warning: Amazon link) and
Davis. Davis is rather out of
date now, but it is published by Dover and is cheap.
It might seem that talking only about the
natural numbers means that none of this is very
interesting. However, with the use of Goedel numbering, any finite sentence over a finite
alphabet can be encoded as a natural number, so
Recursion theory applies to all sorts of structures. One example is the set, X, of (oracle-less) Turing machines. Turing showed that
the subset of X which consists of those machines
which eventually halt after being started with
an empty tape, is not computable. This was
his resolution of the Halting Problem.
Also, it is not a mathematical theorem that 2^N = (omega | c). This statement is the Continuum Hypothesis, and its truth is independant of the standard axioms of set theory (ZF).
Oops.
This is, of course, nonsense. 2^N is indeed equal
to the cardinality of the reals.
The Continuum Hypothesis says that this cardinality is the next largest cardinality after that of the natural numbers.
Is used to denote the cardinality of the set of real numbers. One of my favorite theorems in maths is 2^N = omega, where N is the cardinality of the natural numbers.
It is more usual to denote the cardinality
of the reals with a lower case c.
I have most often seen omega as the first transfinite ordinal (the
ordinal type of the natural numbers,
1, 2, 3,...).
Also, it is not a mathematical theorem
that 2^N = (omega | c). This statement
is the Continuum Hypothesis, and its truth
is independant of the standard axioms of
set theory (ZF).
"I used Deja three or more times a day," said Frank Davies, a student and research assistant at Columbia University, in an e-mail. "I'm enraged that it has been taken from me..."
Yeah! He should demand his money back! What
a ripoff.
The point of 'Capitalists' and 'Conservatives' (usually you find Left/Socialists and Right/Capitalists) is that your gain is *ALWAYS* at the expense of someone else. Its called profit,
Consider the following idealized example.
I want to buy a widget for my home. Having a widget in my home is worth $20 to me (either because of its aesthetic beauty, or because it is a labour saving device.)
You are a maker of widgets. Your factory can make them for $10 (including raw materials, equipment costs, and the labour of the people who work in the factory). Having made a widget for $10, you want to sell it for $15, for a $5 profit (you need to eat.)
So, you and I engage in a transaction. I give you $15, and you give me a widget. I am happy since I have purchased for $15 something which is worth $20 to me: I have made a profit of $5. You are also happy, as you have sold for $15 something that cost $10 to make: you have made a profit of $5.
We both gain from this transaction. Your profit is not my loss, any more than my profit is your loss. The transaction was not zero-sum.
I would like to support the EFF, but I am a guest
in the US (non-resident alien), and as such have reservations about
participating in the American political process.
It's not that I don't have opinions about
various things that happen, but I feel that
as a guest I don't have the right to influence
them. As a foriegn national I'm not eternally
tied to the results of decisions (legal
and otherwise) in the same way that a US citizen
is. I can always go back to my country if I don't like things.
However, in cases involving the net,
actions taken in the US can directly affect
the net everywhere, and the EFF seems like a
good place to get involved. I'm not looking
so much for absolution to join the EFF, but rather
asking how/.'s USAian readership feels
about foriegners trying to influence American
public policy.
Microsoft's new temp rules (effective as of this past July) are that each temp is not allowed to return to work for 100 days following a one-year stretch of employment...No, temps are out of luck for that stretch of time...[I]t's still a
dishonest...practice.
This clause is a way to *protect*
temps from being abused as
permanent-employees-without-benefits.
Suppose MS (or any other company) really
does want a permanent employee, to work on a
long-term project, say. Then the fact that
they'll have to give up any empolyees classified
as "temp" after a year, and not be allowed to hire them back for three
months means they'll be less likely to try to
do an end run around granting benefits by hiring
temps permanently.
A "temp" position is temporary: that's
why it's called a "temp" position, and why
temps get hosed when it comes to benefits.
On this point, at least, MS is doing the
right thing.
The only thing, based on what I've read on pi, that interests mathemations is trying to determine if pi is completely irrational (can't be expressed as a fraction of two integers) -- if there's any point where the digits in pi repeat ad infinitum, pi becomes rational, and most of the current foundation of advanced number theory will have to be rewritten.
Pi was proved to be irrational in 1770. A later, simpler, proof can be found here.
Something that isn't known about pi is whether or not it is "normal". That is, whether
all finite digit sequences of a given length appear with the same frequency in the long run.
Based on the tiny initial segment of pi that has been computed (just a few billion digits) pi "seems" to be normal, but initial segments can be misleading.
"Fine," I say, "then do you really expect me to believe that a Hollerith tabulator took 3-30 hrs per operation? 10^(-4) to 10^(-5)ops/sec (according to the chart) = 10,000-100,000 seconds/op. In fact, there isn't a single computer capable of 1 op/sec until 1950 in the chart. Am I to believe that business spent millions on computers that were far slower than a moderately bright child using an abacus?
I don't have the expertise to comment on the data itself, but your observations don't take into account the caption to the graph:
"operations per second per US$1000 in 1999 dollars [emphasis mine]
I'm sure businesses did indeed spend millions of dollars, and got the indicated number of operations per second for each $1000 they spent, in today's terms. The chart may well be bogus, but not for the reason you suggest.
It does show that the Census Bureau must have spent some serious money on Hollerith's machines.
Cheers, quokka
Re:Good, but he's no Tolkein...
on
The Truth
·
· Score: 1
He didn't like automobiles, for instance.
He liked automobiles a great deal. (See _Mr Bliss_ for example.)
"ash nazg" & all that
Ash nazg means "One ring". I'm not quite sure what point you're trying to make.
Slashdot Mirror
I think the authors have assigned links due to the Vietnam war to Thailand.
Why would anyone name all 6 of their children Frieda?
You must have meant to write something else. Euclid has a simple proof that there are infinitely many primes.
Cheers, quokka
An obvious boneheaded error here is that this should actually be
to "throw away" the bits of A that stores the primes before p_n. Sigh.
quokka.
There are simple functions f(x), for appropriate definitions of "simple". Here is one.
Define the constant A by:
where \sum denotes summation, p_n is the n-th prime, and t_n is the n-th triangular number. Then A = 0.2030050011... In particular, A is a constant, and so "simple". Now define the function
where floor is the integer part truncation of the argument, and T_n is the sum of the first n triangular numbers:
Then, up to bone-headed off-by-one type errors on my part, f(n) = p_n.
You may or may not regard this function as "simple". It is almost certainly not useful for generating primes.
It is not hard to show that no non-constant polynomial can take on only prime values as inputs range over the integers. Rather more interestingly, there are (multi-variate) polynomials whose positive values are exactly the primes, but who also take on a bunch of "junk" negative values.
Cheers, quokka.
Indeed, this is the whole point of using an oracle: it allows the Turing machine to access information that it could not possibly compute for itself. If we restricted oracles to effectivley computable sets then we may as well not use them at all: just replace the oracle with a subroutine that computes the oracle set itself.
It is a mistake to conflate Computability Theory (also called Recursion Theory) and Complexity Theory. The latter is the more important to CS, and involves the analysis of algoriths for efficiency. The former is more abstract (as the use of uncomputable oracles suggests) and concerns itself with questions of the existence (or otherwise) of algorithms, but not their efficiency.
In general, this sentence is not true. I have had very little exposure to the theory of randomness, so I can't make any useful claims about the similarity of it to Computability theory.However, the Halting Problem, as a pioneering result in Computability theory, is quite independent of randomness. Computability Theory is not the same as Complexity Theory (in which statistics plays an essential roles), and it has a large literature which doesn't mention randomness at all.
Cheers,
quokka
Indeed, let K be the set of all (Goedel numbers) of (oracle-less) Turing machines which halt when started with empty input. Then a Turing machine with a K-oracle can trivially solve the Halting Problem: it just examines its input (which will be the Goedel number of a Turing machine) and checks if it lies in K. If so, it answers "yes" and otherwise answers "no".
Turing's theorem is much more interesting that you seem to give it credit for. Let B be a set of natural numbers. Define the "B-Halting Problem" as
Then Turing's proof shows that no Turing machine equipped with only a B-oracle can solve the B-Halting Problem. The usual, oracle-less, version is a special case of this: just take B = empty set.Randomness is not an essential part of the study of Turing machines-with-oracle, and the Halting Problem does not involve randomness at all.
Cheers,
quokka
A (rough) definition goes as follows.
Suppose B is a subset of the natural numbers N = {0, 1, 2, 3, ...}. Then a B-oracle is a device
which can correctly answer any question of the form
"is x an element of B?", where x is a natural
number. By "answer" we mean that given a
natural number x, the oracle will in finite
time answer "yes" or "no", depending on whether
or not x is actually in B.
For some sets (such as the set of primes) we can build an oracle easily: just write a computer program to do it. For the primes the program could look something like this. The number, x, is given:
- If x = 1, answer "NO" and stop.
- Set d = 2.
- If d * d > x, answer "YES" and stop.
- If d divides x, answer "NO" and stop.
- Increment d by one.
- Goto step 3
We don't care that this algorithm is horrifically inefficient: we are just interested in the fact that there is an algorithm to recognize the primes.For most sets though, we can't write a progrem to do this: under the generally accepted notion of "computability" (which comes from Church's Thesis) only countably many subsets of N are computable in this way, while N has uncountably many subsets. In these uncomputable cases, an oracle is assumed to exist as if "by magic."
Now, suppose M is a Turing machine equipped with a B-oracle. This machine is just like an ordinary Turing machine, except it can ask its oracle any question of the form "is x an element of B?".
[One way to imagine M is to assume it has a second, write-only infinte tape, on which is written an infinite string of zeros and ones. The n-th digit is one exactly if n is an element of B. Then, to "consult the oracle", M just reads the appropriate digit on its second tape. Any specific digit on this tape can be reached in a finite number of steps ("finite time"), so the second tape, along with some read logic in the machine itself, acts as the oracle.]
Further suppose that M "recognizes" the set A, which is itself a subset of the naturals. That is, suppose that M acts as an A-oracle, able to correctly answer any question of the form "is x in A?". In this case we say:
This relationship is written A <=_T B (where the underscore represents a subscript, and the ugly '<=' is meant to represent the "less than or equal" sign.)If A <=_T B and B <=_T A then we write A =_T B and say that A and B are Turing equivalent. From the stand point of computation, A and B are essentially the same.
However, the real interest lies in the relation <=_T itself. This relation turns out to give an extremely rich structure to the subsets of the natural numbers, and is the subject of much mathematical research. The modern standard reference for this field is Soare. This is targetted at graduate students and upper-level undergraduates. Other good references are Rogers (warning: Amazon link) and Davis. Davis is rather out of date now, but it is published by Dover and is cheap.
It might seem that talking only about the natural numbers means that none of this is very interesting. However, with the use of Goedel numbering, any finite sentence over a finite alphabet can be encoded as a natural number, so Recursion theory applies to all sorts of structures. One example is the set, X, of (oracle-less) Turing machines. Turing showed that the subset of X which consists of those machines which eventually halt after being started with an empty tape, is not computable. This was his resolution of the Halting Problem.
Cheers,
quokka
Cheers, quokka
This is, of course, nonsense. 2^N is indeed equal to the cardinality of the reals.
The Continuum Hypothesis says that this cardinality is the next largest cardinality after that of the natural numbers.
Cheers, quokka
Also, it is not a mathematical theorem that 2^N = (omega | c). This statement is the Continuum Hypothesis, and its truth is independant of the standard axioms of set theory (ZF).
Cheers, quokka.
Cheers, quokka
I want to buy a widget for my home. Having a widget in my home is worth $20 to me (either because of its aesthetic beauty, or because it is a labour saving device.)
You are a maker of widgets. Your factory can make them for $10 (including raw materials, equipment costs, and the labour of the people who work in the factory). Having made a widget for $10, you want to sell it for $15, for a $5 profit (you need to eat.)
So, you and I engage in a transaction. I give you $15, and you give me a widget. I am happy since I have purchased for $15 something which is worth $20 to me: I have made a profit of $5. You are also happy, as you have sold for $15 something that cost $10 to make: you have made a profit of $5.
We both gain from this transaction. Your profit is not my loss, any more than my profit is your loss. The transaction was not zero-sum.
Cheers, quokka
It's not that I don't have opinions about various things that happen, but I feel that as a guest I don't have the right to influence them. As a foriegn national I'm not eternally tied to the results of decisions (legal and otherwise) in the same way that a US citizen is. I can always go back to my country if I don't like things.
However, in cases involving the net, actions taken in the US can directly affect the net everywhere, and the EFF seems like a good place to get involved. I'm not looking so much for absolution to join the EFF, but rather asking how /.'s USAian readership feels
about foriegners trying to influence American
public policy.
Cheers, quokka
This clause is a way to *protect* temps from being abused as permanent-employees-without-benefits.
Suppose MS (or any other company) really does want a permanent employee, to work on a long-term project, say. Then the fact that they'll have to give up any empolyees classified as "temp" after a year, and not be allowed to hire them back for three months means they'll be less likely to try to do an end run around granting benefits by hiring temps permanently.
A "temp" position is temporary: that's why it's called a "temp" position, and why temps get hosed when it comes to benefits.
On this point, at least, MS is doing the right thing.
Cheers, quokka
A billion times zero is still zero.
Pi was proved to be irrational in 1770. A later, simpler, proof can be found here.
Something that isn't known about pi is whether or not it is "normal". That is, whether all finite digit sequences of a given length appear with the same frequency in the long run. Based on the tiny initial segment of pi that has been computed (just a few billion digits) pi "seems" to be normal, but initial segments can be misleading.
See a description of some cool formulas for doing so.
Trancendentals are numbers which are not the root of any polynomial with *integer* coefficients.
(Note that by definition, polynomials have only finitely many terms. The infinite-term version of a polynomial is a power series.)
I don't have the expertise to comment on the data itself, but your observations don't take into account the caption to the graph:
"operations per second per US$1000 in 1999 dollars [emphasis mine]
I'm sure businesses did indeed spend millions of dollars, and got the indicated number of operations per second for each $1000 they spent, in today's terms. The chart may well be bogus, but not for the reason you suggest.
It does show that the Census Bureau must have spent some serious money on Hollerith's machines.
Cheers,
quokka
Cheers, quokka