Re:MPEG-2 Patents Have Expired
by Godel_unicode on Thursday February 15, 2018 @12:46PM
(#16385944)
First, Shor's algorithm (as an example) cannot be expressed as a Universal Turing Machine. You are thinking much too small, software implementations on Turing Machines are possible for a strict subset of possible algorithms.
Second, even for algorithms which can be expressed as Turing Machines, you are giving the computer science equivalent of saying that a house and it's architecture drawing are the same. One is a thing which exists, one is a description of the thing. You cannot run an unimplemented algorithm without first doing the work of implementing it.
Re:MPEG-2 Patents Have Expired
by thaumasiotes on Thursday February 15, 2018 @01:25PM
(#16386289)
If we lose all of our compilers, processors, etc., would the source code to Windows stop being software?
(1) All computable programs can be expressed as a Universal Turing machine.
(2) There are countably many Universal Turing machines
(3) In an abstract sense, we can thus assign a unique identifier to each possible computer program. I can tell you "run program 383439343" and that will tell you everything you need to run that function.
Most of these programs are of course not correct in the sense that they produce a useful output, or even necessarily terminate. But then, most numbers aren't useful either, it's only because of the emergent properties of our mathematical rules that something like a "prime number" even has a conceptual meaning, and it's only because of our contextual needs that, say, sorting an array would be a useful output.
Distinguishing between algorithms and software is a distinction without a difference. If the two implementations produce a different output, then by definition they must be following a different algorithm. And if they are the same algorithm, then they can be reduced to the same Universal Turing machine.