You are partially right. There is no free lunch in the universe. The cost of computing a perfect hash is, I vaguely recall, on the order of O(n lg n). The point is, no matter how big the results get, calculating the array offset into the table is still O(1). In other words, it's just as cheap to add 2 to 4 as it is to add it to 4000000000000. Since this table will probably be accessed an order of magnitude more often than it will be written, it makes sense to pay for the load on the update side, rather than the access side.
Nope, yourself. Hashing can only have a slowdown when there are collisions. The way you deal with those collisions determines the efficiency of your algorithm. Importantly, there exists an algorithm that guarantees no collisions and is therefore O(1). Checkout Perfect Hashing on Wikipedia for details.
Not quite. Linear time means that for a given hash table, the search time will be the same (assuming no collisions).
Instead of viewing them both as O(1) look at it like O(1) and P(1). The bigger hash table will have a bigger look-up time but still be constant.
Nope. O(1) is O(1). The constant doesn't change with the size of the input. Otherwise, it would be O(whatever relates the "constant" to the input size). A perfect hash, or a chained hash are, in fact, O(1) for lookups. If something is linear time, then it's O(n). But we have efficient algorithms, such as binary search, that are O(lg n).
First, compute the set of tags for your project. You can use ctags *.c *.h, for example, but other programs may also be able to produce a tags file. The format of the tags file is fairly simple. Each line is the tag, followed by a tab, then the relative path to the file containing that tag, followed by a tab, then a regular expression matching the line on which that tag is found. If the tag occurs more than once, just insert new copies of the line with different regexes.
Now for the neat, Vimmy part. When typing in insert mode, press Crtl-N and you will get a completion window that lists all of your tags. Pretty neat, huh?
I`m dead serious. Starting with a language like Java or C++ or *.NET or anything where the programmer can make something interesting means they will focus on the end product and not the code.
Give them a language like pascal, and restrict them to cli apps.. and they won`t spend their time trying to make their app do something cool.. but instead focus on making the code look neat.
Tex was written in Pascal. I would hardly call that useless.
Part of your considerations must of course be what language you teach your course in. Contrary to popular opinion, I claim that Java is a bad choice for several reasons. First, Java is complex. Just getting a program to run requires extensive knowledge of paths and the underlying environment. This takes away from the learning experience. Second, Java can be likened to a box of complex and powerful parts. The problem is that students come to rely upon those parts but fail to learn how they work. Finally, Java constrains one's creativity to one particular mode of thought: the Java object model. This prevents the kind of cleverness and creativity that we need in good programmers.
So then, what language to use? I propose a form of assembly. Perhaps MIPS, for which a number of good simulators, like SPIM, exist. You could also use x86 assembly via GAS, which is the GCC assembler. It is very easy to prepare an assembly file that way, so you can get a program running easily. Also, you can start with the extreme basics by only using registers at first, then graduating to memory. The best partvis that students will naturally learn about the underlying hardware at the same time. Later in the course, you can introduce them to C as a form of generalized assembler, for which purpose it was first intended. Then the students will better appreciate the power and flexibility that C grants. By the end of the course, your students will have a good grasp of exactly what their machine is doing with their program.
IBM didn't sell you anything back then. You leased the machine, rather than buy it. IBM would charge you a low price but ship and install a bigger machine with extra processors and memory modules installed. The lease terms limited you, rather than physical limitations. This was actually a very good thing. First, whenever something broke, IBM could switch it out over the phone, which made those late night calls much more tolerable. Second, if you needed more power, they could switch on more processors and bill you. Then, when you no longer needed the extra, they could switch them off again and save you money. It was really a win-win situation for everyone.
The big difference here is that we are talking about software, not hardware. If MS really does this, it will either be a wild success or a dismal failure. Personally, I will stick with my Mac or move back to Linux.
So, I can pick turing machines that require more space than you can offer. I probably just suck at proofs or don't remember correctly what defines a turing machine, A turing machine is simply a finite state control coupled with an infinite tape and the ability to read a single symbol from that tape, write out a symbol to the current spot on the tape, and determine to move one spot left or right on the tape.
but doesn't your statement also mean some processors/languages normally assumed to be turing machines are not because there exist bigger ones with more ram? The basic argument to the proof is this: Think of a very simple machine, with some registers (at least an accumulator, a PC, and an IR), and a very small amount of RAM. Nothing more. You could visualize all of these registers and memory locations as boxes on a big sheet of paper. Now, line all of these boxes up one after another. Now you have a single, giant, register containing a single number. This number is of finite length, say N bits. Therefore, in binary, there can be no more than 2^N possible numbers that fit in that box. So, write down 2^N boxes, one for each possible number. Read off each of those numbers in turn, load them into the machine's registers and memory and step the clock one cycle. Now, note the new number (which is another of the 2^N states) and draw a line between the corresponding boxes. Do this for every number in the 2^N-sized set of numbers. The result, a finite state automaton, which is exactly equal to some regular expression. (Take the union of all of the accepted starting numbers that result in an "accepting" state where the machine halts.)
The way I'm seeing it is that given an infinite amount of RAM, and then either a FPGA configured to be a CPU through Verilog or any other CPU (say a R3000), they're either both turing machines or not.
Without a RAM limitation, any given set of gates and interconnections can be put onto a FPGA either directly, or emulated through a simpler set of gates and interconnects on the FPGA assisted by a freakin' huge chunk of software dumped into "infinite RAM". Remember, we have never yet built a machine with infinite RAM. Not only that, but we cannot even be certain such a machine could fit in our Universe. So, given an infinite amount of RAM, and a finite state machine, you have a Turing machine. My comment is that we don't have that first condition and probably never will. That means that none of the machines we have ever built are in fact Turing machines. They are merely very complex FSAs that can simulate a Turing machine well enough to get by.
PERL, Ruby, Python, JavaScript (which is more based upon LISP than Java, despite the name), for instance. So, one could learn any of those languages and learn about functional programming from them. You don't have to learn about functional programming from languages that aren't very popular or commonly used.
You can get your feet wet, but to take advantage of many benefits to functional language (for instance, ML's superb type inference, or Erlang's formidable scalability), you need to go unpopular. You are correct, though; functional programming style fits in many languages which are not strictly functional. Oh, I don't know, you can make some pretty big programs with lanugages like PERL, Python, and Ruby. Also, Javascript is no slouch either, and it's based upon Self rather than Java.
I have to completely disagree with OP here. First, Logic Programming is based upon the idea of relations between sets of objects. These relations are usually expressed as equations of some form.
"rules of a system"
Logic programming turns up in many places: type inference (OCAML, CAML, ML, etc.), dependency analysis (the various make's and project builders), databases (think SQL), and spell checking.
All specialized tasks. You might embed Prolog in Word to perform spell checking; you don't write Word in Prolog. None of these tasks are any more specialized than serving up web pages, or processing images, or editing text or any number of other things that one does with computers. Conversely, we can argue that all tasks in computing are specialized. So, what's your point?
All of this to one side, one can note that since the set of all functions is a subset of the set of all relations, lambda calculus can be no more powerful than relational programming. Therefore, Logic Programming is at least as capable of solving a problem as C or the like.
Welcome to the Turing tarpit. Actually, you can create good programs with Logic Programming languages like Prolog. It includes most of the common features of any programming language, including C integration, loops, conditionals, and the like. It's no more of a tarpit than your suggested "unpopular" functional languages. (Erlang's a good example here in that its syntax is about as alien to a C programmer as it can get.)
What is a CPU and what is a programming language? From a comp.sci. point of view, the input language of anything that can execute any algorithm, that is, that is turing complete, is a programming language.
Proof that an FPGA is turing complete: snip...
An FPGA can emulate any set of gates and interconnections given a description of these as input. Actually, it can't. After all, for any FPGA you care to mention, I can pick a set of gates and interconnections that is larger than that FPGA can realize. So, I can pick turing machines that require more space than you can offer. You can use induction to show that this is always the case. Therefore, FPGA's are not Turing complete.
A normal processor, e.g. a Z80 is a set of gates and interconnections. Thus, an FPGA can emulate a Z80. The Z80 assembler is turing complete. Anything that can emulate something that is turing complete given the right input, is turing complete. Thus, and FPGA is a turing complete machine and its input a programming language. Funnily enough, you can show that real CPU's are no more powerful than a simple FSA, and are not Turing complete. This is because you can visualize all of the memory locations, register positions, etc as bits in a very big binary number of length n. Whenever anything happens, that number changes to another number of length n. Since there can never be more than 2^n possible states in this case, the number of states is finite and can be completely described by an FSA. Since that is the case there will be languages that this FSA cannot compute.
I'm going to take each of these on one at a time...
Functional languages seek to express all operations as a chain of functions which operate on data and return other data. "Function" is used in its mathematical sense here. Purely functional languages discourage state, and don't allow mutable variables. The lack of state and mutability give rise to some power; effortless parallelizability, for instance. Well, more specifically, functional languages try to adhere to the precepts of the Lambda Calculus which, among other things, treat programs as data by allowing higher-order functions (functions that can take other functions as arguments and return them as results). This is a defining feature of functional languages, and it turns up in many surprising languages. PERL, Ruby, Python, JavaScript (which is more based upon LISP than Java, despite the name), for instance. So, one could learn any of those languages and learn about functional programming from them. You don't have to learn about functional programming from languages that aren't very popular or commonly used.
Logic languages are something different altogether. They provide a framework for defining the rules of a system, then searching for answers which fit the given rules. Logic programming is not useful for general-purpose tasks, but can hugely reduce programming time in tasks which are difficult to solve any other way. I have to completely disagree with OP here. First, Logic Programming is based upon the idea of relations between sets of objects. These relations are usually expressed as equations of some form. For instance: in the make language (used to build programs) one specifies an equation relating a target to its dependencies. The program (in this case make) then uses a variant of the Unification algorithm to solve these systems of equations, building your program as it does so. Logic programming turns up in many places: type inference (OCAML, CAML, ML, etc.), dependency analysis (the various make's and project builders), databases (think SQL), and spell checking. IIRC MS Word (at least older versions) used a spell checker written in Prolog.
All of this to one side, one can note that since the set of all functions is a subset of the set of all relations, lambda calculus can be no more powerful than relational programming. Therefore, Logic Programming is at least as capable of solving a problem as C or the like.
"Programmers still needed debugging tools, of course, but debugger vendors in 2047 distributed numbered copies only, and only to officially licensed and bonded programmers. The debugger Dan used in software class was kept behind a special firewall so that it could be used only for class exercises." -- Richard Stallman, The Right to Read
You mean aside from our system of writing and morphology and a good part of our language? The characters that you are reading right now are the distant children of roman letters. In fact, the CAPITAL LETTERS are taken directly from the Trajan column, which is from the Romans. The minuscules that we normally use in words are a Carolingian modification of the original Trajan Capitals.
Oh, jeeze. I think I just got it. Sorry for the rant.
Please define for me now the function that you would use to accurately determine the age of the participants of a purported piece of drawn child pornograpy. Your function, in order to be useful, must not trigger in the case of false positives. To do so would prevent legitimate artwork—under this law—from receiving legal protection. Go ahead, try, I'll wait.
So, could you do it? What did your attempt at solution use? Facial recognition? Body size? Use of accepted child stereotypes like pigtails or silly clothing? How do you account for the edge cases where the depicted figure was a shape–shifter, or had their mind transplanted into a 12–year old clone of themselves? How about the case where they are a depiction of a person who is older than they look, or a depiction of a non–human that is very old and wise, yet somehow has the body of a 12–year old? It can probably be shown that just these edge cases make the problem of selecting cartoon child pornography undecidable. The addition of all of the other edge cases that you would have to account for almost certainly make the problem undecidable.
The fundamental problem with these sorts of regulations and these sorts of arguments are the assumptions that they must inevitably make. You assume that there is some sort of function that correctly maps depictions of people onto their ages without accounting for the author's drawing style, the intended story, or the simple fact that these are nothing more than marks on paper or glowing lights on a screen that are being interpreted by the reader! Further, you assume a causal relationship—in the absence of any supporting evidence, and with an overwhelming amount of contradictory evidence—between depictions of depravity and the desire to commit such acts of depravity. I don't know about other people but, when I watch a violent movie (or a news report), I am not suddenly filled with an overwhelming urge to go out and kill someone. I further posit that those who are filled with such desires have a pre–existing condition that has not been properly addressed by the society that idiots like you purport to be concerned with.
Although I cannot offer proof that any function to determine violation of this law is inherently undecidable, I conjecture that it is so. Since we cannot reasonably decide what constitutes a candidate for expulsion under this law, and since we must not censor free speech or censure the authors of such speech, we must err on the side of caution. Furthermore, since we have nothing to gain from such a law—no living organism is harmed at all in the production or consumption of this material—we must not approve such a law. To do so is to invite the kind of vigorous mind control and oppression so recently practiced by the USSR and still practiced by China and every tin–pot dictatorship in the world today. So, until you can find a concrete and correct method to determine speech that is actually harmful to the speaker, the listener, and society at large in perpetuity, I will continue to argue against ridiculous laws such as these.
As Plato once said, "Quis Custodiet Custodes Ipsos?"
This idea has been had before. There is already a free service that provides a simple and usually fast way to share and watch video torrents. Check out http://participatoryculture.org/ for a player and a broadcaster of your very own.
The design given in TFA is not the same as a Savonius Windmill. While I cannot speak to any improvements in efficiency, I will point out the differences.
The Savonius windmill uses a pair of buckets that allow air to pass from one bucket to another, while TFA's rotor does not. TFA's rotor seems to use the idea that as air moves over the front surface it is pushing while as it moves over the back surface, it creates a lift effect like a wing. This does not appear to be the same process as the Savonius Windmill referenced here.
The other main difference is the addition of extra stators to guide the wind into the system. I get the impression that, like the ducting in a ducted fan assembly, they help to cancel efficiency-stealing wind vortices and help to guide the air in the most optimal manner.
So, while I cannot say whether or not TFA's turbine is more efficient, I can say that it is most certainly not a Savonious windmill.
Slashdot Mirror
You are partially right. There is no free lunch in the universe. The cost of computing a perfect hash is, I vaguely recall, on the order of O(n lg n). The point is, no matter how big the results get, calculating the array offset into the table is still O(1). In other words, it's just as cheap to add 2 to 4 as it is to add it to 4000000000000. Since this table will probably be accessed an order of magnitude more often than it will be written, it makes sense to pay for the load on the update side, rather than the access side.
Nope, yourself. Hashing can only have a slowdown when there are collisions. The way you deal with those collisions determines the efficiency of your algorithm. Importantly, there exists an algorithm that guarantees no collisions and is therefore O(1). Checkout Perfect Hashing on Wikipedia for details.
Not quite. Linear time means that for a given hash table, the search time will be the same (assuming no collisions).
Instead of viewing them both as O(1) look at it like O(1) and P(1). The bigger hash table will have a bigger look-up time but still be constant.
Nope. O(1) is O(1). The constant doesn't change with the size of the input. Otherwise, it would be O(whatever relates the "constant" to the input size). A perfect hash, or a chained hash are, in fact, O(1) for lookups. If something is linear time, then it's O(n). But we have efficient algorithms, such as binary search, that are O(lg n).
Here is a neat one:
First, compute the set of tags for your project. You can use ctags *.c *.h, for example, but other programs may also be able to produce a tags file. The format of the tags file is fairly simple. Each line is the tag, followed by a tab, then the relative path to the file containing that tag, followed by a tab, then a regular expression matching the line on which that tag is found. If the tag occurs more than once, just insert new copies of the line with different regexes.
Now for the neat, Vimmy part. When typing in insert mode, press Crtl-N and you will get a completion window that lists all of your tags. Pretty neat, huh?
.. like pascal!
WAIT WAIT.. this isn't a troll!!
I`m dead serious. Starting with a language like Java or C++ or *.NET or anything where the programmer can make something interesting means they will focus on the end product and not the code.
Give them a language like pascal, and restrict them to cli apps.. and they won`t spend their time trying to make their app do something cool.. but instead focus on making the code look neat.
Tex was written in Pascal. I would hardly call that useless.
Part of your considerations must of course be what language you teach your course in. Contrary to popular opinion, I claim that Java is a bad choice for several reasons. First, Java is complex. Just getting a program to run requires extensive knowledge of paths and the underlying environment. This takes away from the learning experience. Second, Java can be likened to a box of complex and powerful parts. The problem is that students come to rely upon those parts but fail to learn how they work. Finally, Java constrains one's creativity to one particular mode of thought: the Java object model. This prevents the kind of cleverness and creativity that we need in good programmers.
So then, what language to use? I propose a form of assembly. Perhaps MIPS, for which a number of good simulators, like SPIM, exist. You could also use x86 assembly via GAS, which is the GCC assembler. It is very easy to prepare an assembly file that way, so you can get a program running easily. Also, you can start with the extreme basics by only using registers at first, then graduating to memory. The best partvis that students will naturally learn about the underlying hardware at the same time. Later in the course, you can introduce them to C as a form of generalized assembler, for which purpose it was first intended. Then the students will better appreciate the power and flexibility that C grants. By the end of the course, your students will have a good grasp of exactly what their machine is doing with their program.
IBM didn't sell you anything back then. You leased the machine, rather than buy it. IBM would charge you a low price but ship and install a bigger machine with extra processors and memory modules installed. The lease terms limited you, rather than physical limitations. This was actually a very good thing. First, whenever something broke, IBM could switch it out over the phone, which made those late night calls much more tolerable. Second, if you needed more power, they could switch on more processors and bill you. Then, when you no longer needed the extra, they could switch them off again and save you money. It was really a win-win situation for everyone.
The big difference here is that we are talking about software, not hardware. If MS really does this, it will either be a wild success or a dismal failure. Personally, I will stick with my Mac or move back to Linux.
Why, thank you!
Without a RAM limitation, any given set of gates and interconnections can be put onto a FPGA either directly, or emulated through a simpler set of gates and interconnects on the FPGA assisted by a freakin' huge chunk of software dumped into "infinite RAM". Remember, we have never yet built a machine with infinite RAM. Not only that, but we cannot even be certain such a machine could fit in our Universe. So, given an infinite amount of RAM, and a finite state machine, you have a Turing machine. My comment is that we don't have that first condition and probably never will. That means that none of the machines we have ever built are in fact Turing machines. They are merely very complex FSAs that can simulate a Turing machine well enough to get by.
You can get your feet wet, but to take advantage of many benefits to functional language (for instance, ML's superb type inference, or Erlang's formidable scalability), you need to go unpopular. You are correct, though; functional programming style fits in many languages which are not strictly functional. Oh, I don't know, you can make some pretty big programs with lanugages like PERL, Python, and Ruby. Also, Javascript is no slouch either, and it's based upon Self rather than Java. I have to completely disagree with OP here. First, Logic Programming is based upon the idea of relations between sets of objects. These relations are usually expressed as equations of some form.
"rules of a system"
Logic programming turns up in many places: type inference (OCAML, CAML, ML, etc.), dependency analysis (the various make's and project builders), databases (think SQL), and spell checking.
All specialized tasks. You might embed Prolog in Word to perform spell checking; you don't write Word in Prolog. None of these tasks are any more specialized than serving up web pages, or processing images, or editing text or any number of other things that one does with computers. Conversely, we can argue that all tasks in computing are specialized. So, what's your point? All of this to one side, one can note that since the set of all functions is a subset of the set of all relations, lambda calculus can be no more powerful than relational programming. Therefore, Logic Programming is at least as capable of solving a problem as C or the like.
Welcome to the Turing tarpit. Actually, you can create good programs with Logic Programming languages like Prolog. It includes most of the common features of any programming language, including C integration, loops, conditionals, and the like. It's no more of a tarpit than your suggested "unpopular" functional languages. (Erlang's a good example here in that its syntax is about as alien to a C programmer as it can get.)
Proof that an FPGA is turing complete: snip... An FPGA can emulate any set of gates and interconnections given a description of these as input. Actually, it can't. After all, for any FPGA you care to mention, I can pick a set of gates and interconnections that is larger than that FPGA can realize. So, I can pick turing machines that require more space than you can offer. You can use induction to show that this is always the case. Therefore, FPGA's are not Turing complete. A normal processor, e.g. a Z80 is a set of gates and interconnections.
Thus, an FPGA can emulate a Z80.
The Z80 assembler is turing complete.
Anything that can emulate something that is turing complete given the right input, is turing complete.
Thus, and FPGA is a turing complete machine and its input a programming language. Funnily enough, you can show that real CPU's are no more powerful than a simple FSA, and are not Turing complete. This is because you can visualize all of the memory locations, register positions, etc as bits in a very big binary number of length n. Whenever anything happens, that number changes to another number of length n. Since there can never be more than 2^n possible states in this case, the number of states is finite and can be completely described by an FSA. Since that is the case there will be languages that this FSA cannot compute.
All of this to one side, one can note that since the set of all functions is a subset of the set of all relations, lambda calculus can be no more powerful than relational programming. Therefore, Logic Programming is at least as capable of solving a problem as C or the like.
"Programmers still needed debugging tools, of course, but debugger vendors in 2047 distributed numbered copies only, and only to officially licensed and bonded programmers. The debugger Dan used in software class was kept behind a special firewall so that it could be used only for class exercises."
-- Richard Stallman, The Right to Read
You mean aside from our system of writing and morphology and a good part of our language? The characters that you are reading right now are the distant children of roman letters. In fact, the CAPITAL LETTERS are taken directly from the Trajan column, which is from the Romans. The minuscules that we normally use in words are a Carolingian modification of the original Trajan Capitals.
Oh, jeeze. I think I just got it. Sorry for the rant.
Please define for me now the function that you would use to accurately determine the age of the participants of a purported piece of drawn child pornograpy. Your function, in order to be useful, must not trigger in the case of false positives. To do so would prevent legitimate artwork—under this law—from receiving legal protection. Go ahead, try, I'll wait.
So, could you do it? What did your attempt at solution use? Facial recognition? Body size? Use of accepted child stereotypes like pigtails or silly clothing? How do you account for the edge cases where the depicted figure was a shape–shifter, or had their mind transplanted into a 12–year old clone of themselves? How about the case where they are a depiction of a person who is older than they look, or a depiction of a non–human that is very old and wise, yet somehow has the body of a 12–year old? It can probably be shown that just these edge cases make the problem of selecting cartoon child pornography undecidable. The addition of all of the other edge cases that you would have to account for almost certainly make the problem undecidable.
The fundamental problem with these sorts of regulations and these sorts of arguments are the assumptions that they must inevitably make. You assume that there is some sort of function that correctly maps depictions of people onto their ages without accounting for the author's drawing style, the intended story, or the simple fact that these are nothing more than marks on paper or glowing lights on a screen that are being interpreted by the reader! Further, you assume a causal relationship—in the absence of any supporting evidence, and with an overwhelming amount of contradictory evidence—between depictions of depravity and the desire to commit such acts of depravity. I don't know about other people but, when I watch a violent movie (or a news report), I am not suddenly filled with an overwhelming urge to go out and kill someone. I further posit that those who are filled with such desires have a pre–existing condition that has not been properly addressed by the society that idiots like you purport to be concerned with.
Although I cannot offer proof that any function to determine violation of this law is inherently undecidable, I conjecture that it is so. Since we cannot reasonably decide what constitutes a candidate for expulsion under this law, and since we must not censor free speech or censure the authors of such speech, we must err on the side of caution. Furthermore, since we have nothing to gain from such a law—no living organism is harmed at all in the production or consumption of this material—we must not approve such a law. To do so is to invite the kind of vigorous mind control and oppression so recently practiced by the USSR and still practiced by China and every tin–pot dictatorship in the world today. So, until you can find a concrete and correct method to determine speech that is actually harmful to the speaker, the listener, and society at large in perpetuity, I will continue to argue against ridiculous laws such as these.
As Plato once said, "Quis Custodiet Custodes Ipsos?"
This idea has been had before. There is already a free service that provides a simple and usually fast way to share and watch video torrents. Check out http://participatoryculture.org/ for a player and a broadcaster of your very own.
The design given in TFA is not the same as a Savonius Windmill. While I cannot speak to any improvements in efficiency, I will point out the differences.
The Savonius windmill uses a pair of buckets that allow air to pass from one bucket to another, while TFA's rotor does not. TFA's rotor seems to use the idea that as air moves over the front surface it is pushing while as it moves over the back surface, it creates a lift effect like a wing. This does not appear to be the same process as the Savonius Windmill referenced here.
The other main difference is the addition of extra stators to guide the wind into the system. I get the impression that, like the ducting in a ducted fan assembly, they help to cancel efficiency-stealing wind vortices and help to guide the air in the most optimal manner.
So, while I cannot say whether or not TFA's turbine is more efficient, I can say that it is most certainly not a Savonious windmill.
Doesn't the iPod play MP3s too? IIRC it does, which means that any source of MP3 data is usable on an iPod. How is that restrictive?