> This article isn't about an imaginary computer with an infinitely long paper tape from a thought experiment, it's about a real computer, just like the ones many HN readers work with every day.
If you're determined to throw out any concepts which technically only apply to theoretical computers with unbounded memory, then go all the way. Your actual physical computer can trivially iterate through all of its possible states in a fixed amount of time. The halting problem is trivially solvable for all programs that your actual physical computer can execute. Your actual physical computer isn't even Turing complete.
Re:The true cost of linked lists
by tialaramex on Monday June 06, 2022 @03:12PM
(#31644601)
> Your actual physical computer can trivially iterate through all of its possible states in a fixed amount of time.
Nope. You're in an imaginary world again. This universe will cease to support computation a long time before it would be possible for the computer to try all possible states.
Sure, but that's like saying that your computer could experience power outages or hardware failures at any time. That's true, but we don't normally consider those as limitations to the computational capabilities of your computer.
Re:The true cost of linked lists
by tialaramex on Monday June 06, 2022 @05:47PM
(#31646781)
It's a difference in kind. The computer could experience a power outage, it could experience a hardware failure, but regardless it and all other real computers will cease to operate long before it would be able to explore all possible states.
I don’t think it’s a difference in kind. Given some specific physical computer, how would you determine an n such that n states are iterable on that computer but n+1 states are not iterable due to the universe’s ability to support computation?
Algorithms and programs are different things. An implementation of the algorithm is called a program. Big-O is used for comparing of algorithms. An algorithm can be implemented in different ways. Performance of the program can be measured precisely. Different implementations of the same algorithm will have different performance. When precise information is available, assumptions are useless. When precise information is not available, at design stage, assumptions are used to compare different algorithms.
As a result k*N can actually be bigger than N^2 when in fact N isn't "an integer" in a mathematical sense but merely a 32-bit machine integer, for example - simply by k being more than 4 billion in that case.