News for hackers. Stuff that matters.

A comment on Ask HN: Why do many CS graduates lack foundational knowledge?. Parent comment

Re:Ask HN: Why do many CS graduates lack foundational knowle... by rrobukef on Monday March 20, 2023 @08:34AM (#35230589)
A Turing machine is a mathematical concept. It has, by definition, infinite memory. A computer is just a real machine that can do similar things as a Linear Bounded Automaton, a Turing machine's little brother who'll never do quite the same things.
[ Parent | on HN ]
Re:Ask HN: Why do many CS graduates lack foundational knowle... by thrown123098 on Monday March 20, 2023 @09:31AM (#35231230)
Wrong: https://en.wikipedia.org/wiki/Arbitrarily_large
[ Parent | on HN ]
Re:Ask HN: Why do many CS graduates lack foundational knowle... by rrobukef on Monday March 20, 2023 @03:07PM (#35236941)
There is a physical limit to the number of disks you can add to your CPU. There is a physical limit to the memory you can address in your CPU (48-bits). It is not arbitrarily large.

Also wrong for Turing Machines, it really is infinite. That's a big difference to arbitrarily large. The halting problem is undecidable for TM's but not for arbitrarily large (you'll need precise definitions though).

[ Parent | on HN ]
Re:Ask HN: Why do many CS graduates lack foundational knowle... by thrown123098 on Monday March 20, 2023 @06:44PM (#35239906)
It is left as an exercise to the reader to find a natural number which isn't arbitrarily large but calculable.
[ Parent | on HN ]
Re:Ask HN: Why do many CS graduates lack foundational knowle... by rrobukef on Tuesday March 21, 2023 @03:08AM (#35243289)
The tape size needed for a Turing machine is incalculable. Here's a reference to a proof: https://scottaaronson.blog/?p=2725.

The machine with 7918-states, Z, stops (well, Z cannot be proven to run infinitly long) iff. ZFC is consistent. For this it needs a finite amount of space but we cannot calculate how much. If we could calculate an upper bound we've proven ZFC is consistent.

[ Parent | on HN ]
Re:Ask HN: Why do many CS graduates lack foundational knowle... by thrown123098 on Tuesday March 21, 2023 @08:23AM (#35245217)
Yes which is why the size if strictly finite but arbitrarily large.
[ Parent | on HN ]