LawMeme LawMeme Yale Law School  
LawMeme
Search LawMeme [ Advanced Search ]
 
 
 
 
Undecidability, Turing Machines, and the INDUCE Act (IICA)
Posted by James Grimmelmann on Tuesday, August 03 @ 17:17:19 EDT Copyright
Ernie Miller's up to 76 items in his comprehensive coverage of the INDUCE Act. One of the latest items to go on "Hatch's Hit List" of technologies the Act might make illegal is the universal Turing machine. Brilliant. See inside for a little mathematico-legal bagatelle on the idea.

First, some technical background. (Computer scientists can skip ahead two paragraphs)

The Turing machine is the classic theoretical model of how a computer works. The model is almost absurdly simple, and yet for every possible computer program, there is a Turing machine that does the same thing. A "universal" Turing machine is one that is capable of simulating any other Turing machine -- the point of the model is that universal Turing machines actually exist.

Among other things, this means that once you have a computer fancy enough to simulate a universal Turing machine (which is almost any computer, since they're so simple) and enough time and memory, your computer can do anything any Turing machine at all can do, which is anything any computer at all can do.

Ernie's point is that a universal Turing machine is just "simulat[ing] copyrighted descriptions of other Turing machines" and therefore would run afoul of the INDUCE Act -- since the only use for a universal Turing machine is to copy what another Turing machine does. Thus, while some Turing machines might be legitimate, universal ones are just devices for copying copyrighted descriptions of other Turing machines.

Ready for the punch line?

One of the things that Alan Turing proved about Turing machines (taking advantage of the simplicity of the model) is that it is undecidable to determine whether two Turing machines do the same thing. Sometimes, you may be able to figure it out, but in general, there is no guaranteed way to know whether Turing machines A and B do the same thing as each other.

But if Turing machine B happened to be a universal Turing machine . . . . why, then . . . my goodness . . . it can't be . . . it must be . . . . it's undecidable whether Turing machine A is a universal Turing machine. There is no guaranteed way to know whether a given Turing machine is universal. That's a proven mathematical fact; computer scientists will swear up and down to its truth.

So if Ernie is right that INDUCE would make universal Turing machines illegal, and if it would leave non-universal Turing machines legal, then we'd have a law such that it's impossible to tell in general whether a particular device is legal or not. There would be some easy cases, sure, but the hard cases would be honestly and truly intractible.

I'm not quite sure what a court would do with a law that could be proven impossible to apply correctly. One possibility is that a law requiring courts to make distinctions no court could possibly make is terminally irrational. Another, closely related, is that a law which forbids things impossible to distinguish from the things it allows is terminally vague. Or, you might have to reformulate the law to avoid the trouble -- perhaps universal Turing machines are okay, or all Turing machines are illegal. Either way, Ernie's point is even stronger: the INDUCE Act is just plain dumb. Even people who want stonger copyright protections should prefer a law that's clearer and has fewer unintended consequences.

 
Related Links
· More about Copyright
· News by James Grimmelmann


Most read story about Copyright:
Top Ten New Copyright Crimes

Options

 Printer Friendly Page  Printer Friendly Page

 Send to a Friend  Send to a Friend

Threshold
  
The comments are owned by the poster. We aren't responsible for their content.

[No Subject] (Score: 0)
by Anonymous on Thursday, August 12 @ 17:14:11 EDT
I like this!

WoList.com [www.wolist.com] - the best site's directory, powerful web search. Advertise with us!
http://www.wolist.com [www.wolist.com]


[ Reply to This ]


Re: Undecidability, Turing Machines, and the INDUCE Act (IICA) (Score: 1)
by cwitty on Tuesday, August 03 @ 19:32:50 EDT
(User Info | Send a Message)
This isn't new to the INDUCE Act. Any software patent has the same problem; to a lesser extent, so do any patent or copyright.

For instance, if we assume that unlicensed MP3 encoders are illegal, then the court must decide whether a given program is an MP3 encoder -- but this is an undecidable problem, in just the same way that it is undecidable whether a program is a universal Turing machine.

For copyright issues, suppose that a target of a RIAA filesharing lawsuit claims that the files being shared are actually outputs from a hardware random number generator, and it's just a coincidence that they happen to be bit-for-bit identical to MP3's of copyrighted songs. There is no way to prove (in the sense of mathematical proof) that he's not telling the truth.


[ Reply to This ]


Re: Undecidability, Turing Machines, and the INDUCE Act (IICA) (Score: 0)
by Anonymous on Wednesday, August 04 @ 16:38:19 EDT
Didn't we go through this whole thing with the proposal to XOR mp3s together? The INDUCE Act is dumb. But it's not dumb because it's going to make Clarence Thomas require an arbitrarily long amount of time to figure out whether my digital camera can run PRODOS.


[ Reply to This ]


Leges humanae nascuntur, vivunt, moriuntur
Human laws are born, live, and die

Contributors retain copyright interests in all stories, comments and submissions.
The PHP-Nuke engine on which LawMeme runs is copyright by PHP-Nuke, and is freely available under the GNU GPL.
Everything else is copyright copyright 2002-04 by the Information Society Project.

This material may be distributed only subject to the terms and conditions
set forth in the Open Publication License, v1.0 or later.
The latest version is currently available at http://www.opencontent.org/openpub/.

You can syndicate our news with backend.php



Page Generation: 0.166 Seconds