Consider the USB problem: \"Given n USB sticks each of size x and m computer fil
ID: 656434 • Letter: C
Question
Consider the USB problem: "Given n USB sticks each of size x and m computer files of size yi, y2, y3, ym, is it possible to copy all the files onto the given USB sticks?" This is a decision problem, where the answer is either yes or no. How hard is this problem? there are 2 steps to showing that a problem is NP-Complete. First show the problem is in NP by describing a polynomial time verifier. Then use proof by reduction with an existing NP-Complete problem. I recommend using the approach shown in class, where you use one solution to implement the other in modern pseudo-code.Explanation / Answer
yes, this admits that this is decidable for modern computers. But it's decidable for a specific machine. If you add a USB drive with disk space, or the ability to store on a network, or anything else, then the machine has changed and the result doesn't still hold.
The thing is, Turing machines don't have an infinite amount of memory. There's never a time where an infinite amount of symbols are written to the tape. Instead, a Turing machine has "unbounded" memory, meaning that you can keep getting more sources of memory when you need it. Computers are like this. You can add RAM, or USB sticks, or hard drives, or network storage. Yes, you run out of memory when you run out of atoms in the universe. But having unlimited memory is a much more useful model.