[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: more evil firmwares found

Jochen Voss <voss@seehuhn.de> wrote:
> On Fri, Apr 23, 2004 at 08:26:35PM +1000, Herbert Xu wrote:
>> Given any finite string of bits, you can construct a Turing machine in a
>> deterministic way and execute it.
> Sorry, I can't follow here.  What do you mean by "construct a
> Turing machine in a deterministic way"?  What would be the Turing
> machine for
>    101011110100000000000000110101000000000000111010100000001

Given any Turing machine M there is a Turing machine N that turns its
input s and writes out a new Turing machine M' that is equivalent to
M operating with s as the input.

This gives you a mapping (realised using N) from the set of finite strings
to the set of Turing machines.

Think of it another way, there exists a C program that can enumerate all
valid C programs.  Just generate all strings of length 1, 2, etc. and use
gcc to validate its syntax (let's assume that gcc halts on all input :) and
print out the valid ones.
Debian GNU/Linux 3.0 is out! ( http://www.debian.org/ )
Email:  Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Reply to: