News for hackers. Stuff that matters.
Re:Turing completeness bullshit by xyzzyz on Wednesday September 28, 2011 @12:06PM (#3048551)
Of course it makes more sense to model real life computers as LBAs. Still, it does not change the fact that given a computer, it has bounded, and not linearly bounded amount of memory, and that makes them no stronger than regular expressions. Of course that there's no practical difference for programmers. Of course the problem space is usually small enough. But it only proves my point: applying abstract terminology to real-life stuff does not necessarily make sense all the time.

It makes more sense to take. say, C or Python programming environment, instead of x86, as a computing model. It's enough to assume that malloc never fails to have genuinely Turing complete device.

Re:Turing completeness bullshit by djcapelis on Wednesday September 28, 2011 @11:59PM (#3051074)
> and that makes them no stronger than regular expressions

Again, no. This is simply not how computational complexity works and this statement is factually incorrect. Please do your research.

Re:Turing completeness bullshit by xyzzyz on Friday September 30, 2011 @08:33PM (#3059021)
Assuming that computer has finitely many states to be in because of finiteness of its memory, we can model it as a very large deterministic finite automaton. You cannot model a real computer as a LBA, because you don't necessarily have as many read-write memory as your input takes. If you think I'm wrong, please, tell me what makes you think that you can model real computers as LBAs.