Hacker News Reader

Algorithms and complexity theory are independent of any physical model of computation; they capture what it means to compute.

The entire field of theoretical computer science stands as a counterexample to your comment. Computer science is not about software engineering.

An algorithm that is infinitly complex and takes infinite time is of no practical use in every day computation. Maybe in theory, in textbooks, in labcoats, but not in industry.

I don't know where an uncomputable algorithm would be useful.

I do know that you cannot possibly start a student out on a plane of the purely theoretical as they cannot see the value of what they are learning, they cannot understand the implications of the material, and frankly they won't remember it if they don't need it. To their minds, they don't need it if they haven't used it. It can be JFM (Just Fking Magic) to them if they haven't seen a case where it has improved their own algorithms. They will also not really understand how it works with no implementation. It is impractical to say the least.

Theoretical computation is a higher level topic then real computation topic. In the same sense that you start math with addition, subtraction, multiplication, and division you should start out computer science with implementation.

Nobody is talking about "infinite time" algorithms; complexity theory concerns itself with what is efficiently computable. This might not directly correspond to "real-world" efficiency, because an algorithm, while polynomial-time, but have poor constants or a huge polynomial.

However, this does not mean complexity theory is useless; it still informs us of what computers can and cannot efficiently do. It marks the limits of feasible computation.

> I don't know where an uncomputable algorithm would be useful.

Complexity theory also does not concern itself with uncomputable algorithms, so that point is irrelevant.

As you say, starting off students with abstract theory doesn't help, because they're unlikely to use it and so it won't stick. However, the same argument goes for your "bottom-up" approach; most students of computer science will not ever have to twiddle bits and manipulate assembly; knowledge of this material would thus be quickly forgotten.

My point, as stated in another comment of mine in this thread, is that it is not necessary that a "true computer scientist" know anything about low-level computer details. I suspect this holds true not only for theoreticians, but also many systems builders (like in distributed systems and such). So, having a intro course focusing on low-level details as the main component will not necessarily provide a good introduction to computer science.

> Complexity theory also does not concern itself with uncomputable algorithms, so that point is irrelevant.

I do not think this is a correct statement from what I've seen.

> As you say, starting off students with abstract theory doesn't help, because they're unlikely to use it and so it won't stick. However, the same argument goes for your "bottom-up" approach; most students of computer science will not ever have to twiddle bits and manipulate assembly; knowledge of this material would thus be quickly forgotten.

If the course is organized correctly the experiance can be magical. You're pulling the curtian on the the giant talking head. You're showing the students how everything works and you should do this directly. Like all teaching the student needs to THINK they have been the ones to discover something while in reality the teacher is supposed to have errected an artificial situation where in this was the case.

You don't start them off with bits right off the bat although that is one approche (That is extremely successful: see NAND 2 Tetris). Like I said in my other comment you state them off with a broken machine. You give them an artifical reason to continue. "If you want to get a grade you have to open up this machine and, with me coupled with some hand holding, diagnose the problem." That gives them a reason to learn about the different parts of the computer. That errects a situation where they FEEL that have found something that they weren't meant to. They've explored something when in reality it was all, as someone smarter then me once said, a "Head Fake". Get them looking at a nearer goal and they'll start dreaming of further ones.

But is the point of your course computer science, or computer engineering. I don't think I'm particularly special, but I have taken just the one computer architecture course as an undergrad (and I don't remember much if any of what I learnt), and now I just completed the first sem of my PhD in computer science. I haven't used the information I learnt in that class yet, even though I'm in a partially applied field (security and cryptography).

All I'm pushing back is on the idea that learning the intricacies of modern computing is necessary for being good at computer science.

EDIT: And wrt complexity theory and computability: there is a subfield of mathematics called computability theory that concerns itself with various notions of what is and isn't computable. Complexity theory concerns itself instead with what is efficiently computable; the problems it considers are already computable.

Well you're not going to like when I say this.

Cryptography isn't Computer Science. It uses some things that Computer Science developed but it isn't Computer Science. It's applied Math.

If Cryptography is in CS then Nuclear Reactor Operations is in CS. NRO uses computers for monitoring systems and develops algorithms to detect certian... ahm... undesierable states. That doesn't mean we should move a reactor into the CS building at every college near you (although I'd love to work on one eventually, sounds like cool work).

Academics may think that crypto is a CS field but the work involved has absolutly nothing to do with CS. For example, all cryptographic functions can be implemented in hardware. If you are building a cryptographic function in hardware, you're not part of the Electical Engineering department or the Mechanical Engineering department you are still in the Math department because all you're doing is implementing an abstract design.

(Insert unintelegable "get off my lawn" statement)

... what?

I am not sure what your idea aof cryptography is, but crypto relates to the most basic of questions about computation: what is and isn't efficiently computable, that is, P ?= NP.

You do realise that the origin of the field of Computer Science lies in mathematics, specifically Turing's work, right? By your argument, the entire field of Theoretical Computer Science is ... not a part of computer science. Some how, I think that that's not quite right.

Computer science assumes that the code is run on a machine with a very specific set of operations since otherwise you wouldn't be able to calculate time complexity. The set of operations were deliberately chosen to be a reasonable abstraction of a modern computer. Thus computer science would look very differently if computers had different capabilities.

For example, lets say that a new computer could switch places of two blocks of memory in constant time no matter their sizes. That would completely revolutionize computer science since many of our old results hinges on the fact that moving memory takes linear time.

The extended Turing thesis says that whatever is efficiently computable in one "reasonable" model of computation, is also efficiently computable in another reasonable model of computation.

Of course, the truth of this thesis has been called into question with the advent of quantum computers, but it holds otherwise.

> A computer sceince background inherently implies software development background.

> An algorithm that takes infinite time for 1 instruction is O(1) and still constant time.

> An algorithm that takes infinite memory for every run is still a constant memory complexity.

None of these are true.

> An algorithm that takes infinite time

Can you give an example of such an algorithm? My understanding of an algorithm is that it must terminate in a finite amount of time, but maybe you have a different definition of an algorithm

> My understanding of an algorithm is that it must terminate in a finite amount of time

Any practical algorithm yes. Any theoretical algorithm no. This is where the will it hault questions come from. Check out Ackerman's function as a good example that we aren't sure if it will terminate. It is still extremely interesting from an algorithms analysis perspective but not from a CS (as I use it) perspective.

Also I'm not specifically talking about algorithms. I'm talking about flaws in O() notation in practice. It is easy to make something look fast in theory when it is far slower in practice.

The algorithm that computes Ackerman's function recursively (https://en.m.wikipedia.org/wiki/Ackermann_function) always terminates in finite time