Re: Implausibility continued (in C)

In this episode, I give Glenn a magic box which doesn't turn out to be
quite as useful as he'd hoped, and I get to cut and paste several large
numbers.....

On Thu, 20 Sep 2007 08:35:56 -0700, someone3 wrote:

<snip>

The issue here is that I am talking about predicting what the computer
will do a certain period of time ahead.

Precisely.

You aren't, you are talking
about whether there is a known answer to a question about an
algorithm.

What did you think the computer was executing if not mathematical
algorithms? (I've got an old Sparcstation that *seems* to run on mashed
potatoes, but I haven't made a complete investigation.)

It's all math, Glenn. Every machine instruction is performing a
well-defined mathematical operation. It's perfectly reasonable to think
about programs mathematically -- in fact, it's much more reasonable to
think about programs this way than, say, molecules.


We are predicting what the computer will do when we step though the
algorithm it will be running. We haven't run it on the computer, we
are just predicting what the computer will do.

By the way, do you think Brownian motion is explainable?

Are you implementing your neural network using Brownian motion? No?
So it's not relevant. As you were so kind to remind me,

The issue here is that I am talking about predicting what the computer
will do a certain period of time ahead.



I'm in an unusually good mood today, so I'm going to give you a present:
a slightly used magical box M that will calculate the exact state of a
machine n steps in the future. It's not quite instantaneous, it has a
few scratches, and it will only work for machines considered in this
thread, but I think you'll enjoy it.

Even using this magic box, there still exist deterministic programs that
are not predictable. Specifically, we don't have a general way of
determining whether or not a program will halt, and this will obviously
have an affect on several other program characteristics. With your new
(to you) box, you might think that all that's necessary is plugging in a
sufficiently large number and seeing if the program is in the halt state.
It's very intuitive to think that, at some finite point, all programs that
are going to stop have stopped, and all the rest of the programs that are
still running must be in an infinite loop.

So what should that limit be? Something big, obviously. A billion? A
trillion? How about the number of atoms in the universe? That's
(roughly) 10^80. But I'm a sneaky ***, remember? How about you make
your guess 10^800, just to be on the safe side. That's 800 zeros, or 10
lines of 80 zeros each.

How steps does the follow program execute?

A: B1R F0L
B: C0R D0R
C: D1L E1R
D: E0L D0L
E: A0R C1R
F: A1L Z1R

You plug it in to your box and get out the answer: >10^800. Is it in an
infinite loop?

Nope.

It runs for 3.0*10^1730 steps and halts.

This is a very pretty number to look at.

steps = 30023277165235628289551030183413401851477543372467\
52500373381801735214240760383265881912082978202876\
69898401786071345848280422383492822716051848585583\
66815379725143861856173020941548768557007853865875\
73048574872220400307698440450988713670876150791383\
11034353164641077919209890837164477363289374225531\
95512602325117225903457015508730368365463087415599\
08225161299384258306913786072736707081901605255340\
77040039226593073997923170154775358629850421712513\
37852708622311268067797375179003293757852001766679\
22468399088559203629337677447608701284468834554778\
06316491601855784426860769027944542798006152693167\
45282133668991746088610648657418901540119403485757\
77182530655416326563343142423255924867001185067165\
81303423271748965426160409797173073716688827281435\
90463944560592817525404832110930600247465896810879\
33819123818123362279928399308330859334788531765747\
02776062858289156568392295963586263654139383856764\
72805139496555440968845657812274329631996080836809\
45364210391495849467580065091609857013289970263017\
08760235500239598119410592142621669614552827244429\
21741646549436389169711396531689266061170929004858\
06775661787157523545940490167192780698328665223329\
23541370293059667996001319376698551683848851474625\
15209456711061545198683989449088568708224497877455\
14532043585886615939797639351028965232958039400236\
73203101744986550732496850436999753711343067328676\
15814626929272337566201561282692410545484965841096\
15740312114406110889753498991567148886819523660180\
86246687712098553077054825367434062671756760070388\
92211743493263344477313878371402373589871279027828\
83771982603800651050757929252394534506229992082975\
79584893448886278127629044163292251815410053522246\
08455276151338393462312908326694937738095046664312\
1689746511996847681275076313206

(Cut 'n' paste courtesy of http://www.drb.insel.de/~heiner/BB )

That's 6 states: 12 reads, 12 writes, 12 moves, and 12 changes of state.

Well, what if instead of using a constant, you used a function? For a
program with n states, what if you calculate your upper limit f() to be:

f(n) = n(^n(^n(^n(^n(^n(^n(^n(^n))))))))

Anything with more steps than this has to be in an infinite loop. Looks
good, right?

What Rado proved is that Sigma(n) [the number of 1s] and S(n) [the number
of steps] are *noncomputable functions*. That means for *any* f(n), there
exists some n where S(n) is going to be much, much bigger than f(n).

The two points I wish to make here are that very simple programs can
exhibit very complex behavior, and that very simple programs can exhibit
non-predictable emergent behavior (in this case, halting or infinite
looping).

With those two points firmly in place, I'd now like to discuss a much more
complex program: your neural network.

Are you willing to do so?

.