逻辑引擎

Sorting network

The following is network-sorting algorithm for less than 33 elements.

What is Sorting Network? Wiki: sorting network

List of sorting networks:
From: sorting networks
Input the number n (maximum 32)
Algorithm choices: “Best”
Click [Take a look] button.

—————————
Zero-one principle

While it is easy to prove the validity of some sorting networks (like the insertion/bubble sorter), it is not always so easy. There are n! permutations of numbers in an n-wire network, and to test all of them would take a significant amount of time, especially when they are larger. However, because of the so-called zero-one principle, far fewer trials are in fact needed to test the validity of a sorting network.

The zero-one principle states that a sorting network is valid if it can sort all 2n sequences of 0s and 1s. This not only drastically cuts down on the number of tests needed to ascertain the validity of a network, it is of great use in creating many constructions of sorting networks as well. The principle has been proven by a special case of the Bouricius’s Theorem in 1954 by W. G. Bouricius.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640

static const unsigned int network02[][2] = {
{ 0, 1},
};
static const unsigned int network03[][2] = {
{ 1, 2},
{ 0, 2},
{ 0, 1},
};
static const unsigned int network04[][2] = {
{ 0, 1}, { 2, 3},
{ 0, 2}, { 1, 3},
{ 1, 2},
};
static const unsigned int network05[][2] = {
{ 0, 1}, { 3, 4},
{ 2, 4},
{ 2, 3}, { 1, 4},
{ 0, 3},
{ 0, 2}, { 1, 3},
{ 1, 2},
};
static const unsigned int network06[][2] = {
{ 1, 2}, { 4, 5},
{ 0, 2}, { 3, 5},
{ 0, 1}, { 3, 4}, { 2, 5},
{ 0, 3}, { 1, 4},
{ 2, 4}, { 1, 3},
{ 2, 3},
};
static const unsigned int network07[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6},
{ 0, 2}, { 3, 5}, { 4, 6},
{ 0, 1}, { 4, 5}, { 2, 6},
{ 0, 4}, { 1, 5},
{ 0, 3}, { 2, 5},
{ 1, 3}, { 2, 4},
{ 2, 3},
};
static const unsigned int network08[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7},
{ 0, 2}, { 1, 3}, { 4, 6}, { 5, 7},
{ 1, 2}, { 5, 6}, { 0, 4}, { 3, 7},
{ 1, 5}, { 2, 6},
{ 1, 4}, { 3, 6},
{ 2, 4}, { 3, 5},
{ 3, 4},
};
static const unsigned int network09[][2] = {
{ 0, 1}, { 3, 4}, { 6, 7},
{ 1, 2}, { 4, 5}, { 7, 8},
{ 0, 1}, { 3, 4}, { 6, 7}, { 2, 5},
{ 0, 3}, { 1, 4}, { 5, 8},
{ 3, 6}, { 4, 7}, { 2, 5},
{ 0, 3}, { 1, 4}, { 5, 7}, { 2, 6},
{ 1, 3}, { 4, 6},
{ 2, 4}, { 5, 6},
{ 2, 3},
};
static const unsigned int network10[][2] = {
{ 4, 9}, { 3, 8}, { 2, 7}, { 1, 6}, { 0, 5},
{ 1, 4}, { 6, 9}, { 0, 3}, { 5, 8},
{ 0, 2}, { 3, 6}, { 7, 9},
{ 0, 1}, { 2, 4}, { 5, 7}, { 8, 9},
{ 1, 2}, { 4, 6}, { 7, 8}, { 3, 5},
{ 2, 5}, { 6, 8}, { 1, 3}, { 4, 7},
{ 2, 3}, { 6, 7},
{ 3, 4}, { 5, 6},
{ 4, 5},
};
static const unsigned int network11[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9},
{ 1, 3}, { 5, 7}, { 0, 2}, { 4, 6}, { 8,10},
{ 1, 2}, { 5, 6}, { 9,10}, { 0, 4}, { 3, 7},
{ 1, 5}, { 6,10}, { 4, 8},
{ 5, 9}, { 2, 6}, { 0, 4}, { 3, 8},
{ 1, 5}, { 6,10}, { 2, 3}, { 8, 9},
{ 1, 4}, { 7,10}, { 3, 5}, { 6, 8},
{ 2, 4}, { 7, 9}, { 5, 6},
{ 3, 4}, { 7, 8},
};
static const unsigned int network12[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11},
{ 1, 3}, { 5, 7}, { 9,11}, { 0, 2}, { 4, 6}, { 8,10},
{ 1, 2}, { 5, 6}, { 9,10}, { 0, 4}, { 7,11},
{ 1, 5}, { 6,10}, { 3, 7}, { 4, 8},
{ 5, 9}, { 2, 6}, { 0, 4}, { 7,11}, { 3, 8},
{ 1, 5}, { 6,10}, { 2, 3}, { 8, 9},
{ 1, 4}, { 7,10}, { 3, 5}, { 6, 8},
{ 2, 4}, { 7, 9}, { 5, 6},
{ 3, 4}, { 7, 8},
};
static const unsigned int network13[][2] = {
{ 1, 7}, { 9,11}, { 3, 4}, { 5, 8}, { 0,12}, { 2, 6},
{ 0, 1}, { 2, 3}, { 4, 6}, { 8,11}, { 7,12}, { 5, 9},
{ 0, 2}, { 3, 7}, {10,11}, { 1, 4}, { 6,12},
{ 7, 8}, {11,12}, { 4, 9}, { 6,10},
{ 3, 4}, { 5, 6}, { 8, 9}, {10,11}, { 1, 7},
{ 2, 6}, { 9,11}, { 1, 3}, { 4, 7}, { 8,10}, { 0, 5},
{ 2, 5}, { 6, 8}, { 9,10},
{ 1, 2}, { 3, 5}, { 7, 8}, { 4, 6},
{ 2, 3}, { 4, 5}, { 6, 7}, { 8, 9},
{ 3, 4}, { 5, 6},
};
static const unsigned int network14[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13},
{ 0, 2}, { 4, 6}, { 8,10}, { 1, 3}, { 5, 7}, { 9,11},
{ 0, 4}, { 8,12}, { 1, 5}, { 9,13}, { 2, 6}, { 3, 7},
{ 0, 8}, { 1, 9}, { 2,10}, { 3,11}, { 4,12}, { 5,13},
{ 5,10}, { 6, 9}, { 3,12}, { 7,11}, { 1, 2}, { 4, 8},
{ 1, 4}, { 7,13}, { 2, 8}, { 5, 6}, { 9,10},
{ 2, 4}, {11,13}, { 3, 8}, { 7,12},
{ 6, 8}, {10,12}, { 3, 5}, { 7, 9},
{ 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12},
{ 6, 7}, { 8, 9},
};
static const unsigned int network15[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13},
{ 0, 2}, { 4, 6}, { 8,10}, {12,14}, { 1, 3}, { 5, 7}, { 9,11},
{ 0, 4}, { 8,12}, { 1, 5}, { 9,13}, { 2, 6}, {10,14}, { 3, 7},
{ 0, 8}, { 1, 9}, { 2,10}, { 3,11}, { 4,12}, { 5,13}, { 6,14},
{ 5,10}, { 6, 9}, { 3,12}, {13,14}, { 7,11}, { 1, 2}, { 4, 8},
{ 1, 4}, { 7,13}, { 2, 8}, {11,14}, { 5, 6}, { 9,10},
{ 2, 4}, {11,13}, { 3, 8}, { 7,12},
{ 6, 8}, {10,12}, { 3, 5}, { 7, 9},
{ 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12},
{ 6, 7}, { 8, 9},
};
static const unsigned int network16[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13}, {14,15},
{ 0, 2}, { 4, 6}, { 8,10}, {12,14}, { 1, 3}, { 5, 7}, { 9,11}, {13,15},
{ 0, 4}, { 8,12}, { 1, 5}, { 9,13}, { 2, 6}, {10,14}, { 3, 7}, {11,15},
{ 0, 8}, { 1, 9}, { 2,10}, { 3,11}, { 4,12}, { 5,13}, { 6,14}, { 7,15},
{ 5,10}, { 6, 9}, { 3,12}, {13,14}, { 7,11}, { 1, 2}, { 4, 8},
{ 1, 4}, { 7,13}, { 2, 8}, {11,14}, { 5, 6}, { 9,10},
{ 2, 4}, {11,13}, { 3, 8}, { 7,12},
{ 6, 8}, {10,12}, { 3, 5}, { 7, 9},
{ 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12},
{ 6, 7}, { 8, 9},
};
static const unsigned int network17[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13}, {15,16},
{ 0, 2}, { 1, 3}, { 4, 6}, { 5, 7}, { 8,10}, { 9,11}, {14,16},
{ 1, 2}, { 5, 6}, { 0, 4}, { 3, 7}, { 9,10}, {14,15}, {13,16},
{ 1, 5}, { 2, 6}, {12,15}, {11,16},
{ 1, 4}, { 3, 6}, {12,14}, {13,15}, { 7,16},
{ 2, 4}, { 3, 5}, {13,14}, {10,15},
{ 3, 4}, { 8,13}, { 9,14}, {11,15},
{ 8,12}, { 9,13}, {11,14}, { 6,15},
{ 9,12}, {10,13}, { 5,14}, { 7,15},
{10,12}, {11,13}, { 0, 9}, { 7,14},
{11,12}, { 0, 8}, { 1,10}, { 4,13},
{ 1, 9}, { 2,11}, { 3,12}, { 5,13},
{ 1, 8}, { 3,11}, { 2, 9}, { 6,13},
{ 2, 8}, { 3,10}, { 7,13}, { 6,11},
{ 3, 9}, { 5,10}, { 7,12},
{ 3, 8}, { 4, 9}, { 7,11},
{ 4, 8}, { 5, 9}, { 7,10},
{ 5, 8}, { 6, 9},
{ 6, 8}, { 7, 9},
{ 7, 8},
};
static const unsigned int network18[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 7, 8}, { 9,10}, {11,12}, {13,14}, {16,17},
{ 0, 2}, { 1, 3}, { 6, 8}, { 9,11}, {10,12}, {15,17},
{ 1, 2}, { 6, 7}, { 5, 8}, {10,11}, {15,16}, {14,17},
{ 4, 7}, { 3, 8}, {13,16}, {12,17},
{ 4, 6}, { 5, 7}, {13,15}, {14,16}, { 8,17},
{ 5, 6}, { 2, 7}, {14,15}, {11,16},
{ 0, 5}, { 1, 6}, { 3, 7}, { 9,14}, {10,15}, {12,16},
{ 0, 4}, { 1, 5}, { 3, 6}, { 9,13}, {10,14}, {12,15}, { 7,16},
{ 1, 4}, { 2, 5}, {10,13}, {11,14}, { 0, 9}, { 6,15}, { 8,16},
{ 2, 4}, { 3, 5}, {11,13}, {12,14}, { 1,10}, { 7,15},
{ 3, 4}, {12,13}, { 1, 9}, { 2,11}, { 5,14}, { 8,15},
{ 3,12}, { 2, 9}, { 4,13}, { 7,14},
{ 3,11}, { 5,13}, { 8,14},
{ 3,10}, { 6,13},
{ 3, 9}, { 7,13}, { 5,10}, { 6,11},
{ 8,13}, { 4, 9}, { 7,12},
{ 5, 9}, { 8,12}, { 7,11},
{ 8,11}, { 6, 9}, { 7,10},
{ 8,10}, { 7, 9},
{ 8, 9},
};
static const unsigned int network19[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 7, 8}, { 9,10}, {12,13}, {14,15}, {17,18},
{ 0, 2}, { 1, 3}, { 6, 8}, {11,13}, {16,18},
{ 1, 2}, { 6, 7}, { 5, 8}, {11,12}, {10,13}, {16,17}, {15,18},
{ 4, 7}, { 3, 8}, { 9,12}, {14,17}, {13,18},
{ 4, 6}, { 5, 7}, { 9,11}, {10,12}, {14,16}, {15,17}, { 8,18},
{ 5, 6}, { 2, 7}, {10,11}, {15,16}, { 9,14}, {12,17},
{ 0, 5}, { 1, 6}, { 3, 7}, {10,15}, {11,16}, {13,17},
{ 0, 4}, { 1, 5}, { 3, 6}, {10,14}, {12,16}, { 7,17},
{ 1, 4}, { 2, 5}, {13,16}, {11,14}, {12,15}, { 0,10}, { 8,17},
{ 2, 4}, { 3, 5}, {13,15}, {12,14}, { 0, 9}, { 1,11}, { 6,16},
{ 3, 4}, {13,14}, { 1,10}, { 2,12}, { 5,15}, { 7,16},
{ 1, 9}, { 3,13}, { 2,10}, { 4,14}, { 8,16}, { 7,15},
{ 3,12}, { 2, 9}, { 5,14}, { 8,15},
{ 3,11}, { 6,14},
{ 3,10}, { 7,14}, { 6,11},
{ 3, 9}, { 8,14}, { 5,10}, { 7,12},
{ 4, 9}, { 8,13}, { 7,11},
{ 5, 9}, { 8,12}, { 7,10},
{ 8,11}, { 6, 9},
{ 8,10}, { 7, 9},
{ 8, 9},
};
static const unsigned int network20[][2] = {
{ 0, 1}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {13,14}, {15,16}, {18,19},
{ 2, 4}, { 7, 9}, {12,14}, {17,19},
{ 2, 3}, { 1, 4}, { 7, 8}, { 6, 9}, {12,13}, {11,14}, {17,18}, {16,19},
{ 0, 3}, { 5, 8}, { 4, 9}, {10,13}, {15,18}, {14,19},
{ 0, 2}, { 1, 3}, { 5, 7}, { 6, 8}, {10,12}, {11,13}, {15,17}, {16,18}, { 9,19},
{ 1, 2}, { 6, 7}, { 0, 5}, { 3, 8}, {11,12}, {16,17}, {10,15}, {13,18},
{ 1, 6}, { 2, 7}, { 4, 8}, {11,16}, {12,17}, {14,18}, { 0,10},
{ 1, 5}, { 3, 7}, {11,15}, {13,17}, { 8,18},
{ 4, 7}, { 2, 5}, { 3, 6}, {14,17}, {12,15}, {13,16}, { 1,11}, { 9,18},
{ 4, 6}, { 3, 5}, {14,16}, {13,15}, { 1,10}, { 2,12}, { 7,17},
{ 4, 5}, {14,15}, { 3,13}, { 2,10}, { 6,16}, { 8,17},
{ 4,14}, { 3,12}, { 5,15}, { 9,17}, { 8,16},
{ 4,13}, { 3,11}, { 6,15}, { 9,16},
{ 4,12}, { 3,10}, { 7,15},
{ 4,11}, { 8,15}, { 7,12},
{ 4,10}, { 9,15}, { 6,11}, { 8,13},
{ 5,10}, { 9,14}, { 8,12},
{ 6,10}, { 9,13}, { 8,11},
{ 9,12}, { 7,10},
{ 9,11}, { 8,10},
{ 9,10},
};
static const unsigned int network21[][2] = {
{ 0, 1}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {13,14}, {16,17}, {19,20},
{ 2, 4}, { 7, 9}, {12,14}, {15,17}, {18,20},
{ 2, 3}, { 1, 4}, { 7, 8}, { 6, 9}, {12,13}, {11,14}, {15,16}, {18,19}, {17,20},
{ 0, 3}, { 5, 8}, { 4, 9}, {10,13}, {15,18}, {16,19}, {14,20},
{ 0, 2}, { 1, 3}, { 5, 7}, { 6, 8}, {10,12}, {11,13}, {17,19}, {16,18}, { 9,20},
{ 1, 2}, { 6, 7}, { 0, 5}, { 3, 8}, {11,12}, {17,18}, {10,16}, {13,19},
{ 1, 6}, { 2, 7}, { 4, 8}, {10,15}, {11,17}, {12,18}, {14,19},
{ 1, 5}, { 3, 7}, {11,16}, {13,18}, { 8,19},
{ 4, 7}, { 2, 5}, { 3, 6}, {11,15}, {14,18}, {13,16}, { 9,19},
{ 4, 6}, { 3, 5}, {12,15}, {14,17}, { 0,11}, { 7,18},
{ 4, 5}, {14,16}, {13,15}, { 0,10}, { 1,12}, { 6,17}, { 8,18},
{14,15}, { 1,11}, { 2,13}, { 5,16}, { 9,18}, { 8,17},
{ 1,10}, { 3,14}, { 4,15}, { 6,16}, { 9,17},
{ 4,14}, { 3,13}, { 2,10}, { 7,16},
{ 4,13}, { 3,11}, { 8,16},
{ 4,12}, { 3,10}, { 9,16}, { 7,13}, { 8,14},
{ 4,11}, { 6,12}, { 9,15}, { 8,13},
{ 4,10}, { 5,11}, { 9,14},
{ 5,10}, { 6,11}, { 9,13},
{ 6,10}, { 8,11}, { 9,12},
{ 7,10}, { 9,11},
{ 8,10},
{ 9,10},
};
static const unsigned int network22[][2] = {
{ 0, 1}, { 3, 4}, { 6, 7}, { 9,10}, {11,12}, {14,15}, {17,18}, {20,21},
{ 2, 4}, { 5, 7}, { 8,10}, {13,15}, {16,18}, {19,21},
{ 2, 3}, { 1, 4}, { 5, 6}, { 8, 9}, { 7,10}, {13,14}, {12,15}, {16,17}, {19,20}, {18,21},
{ 0, 3}, { 5, 8}, { 6, 9}, { 4,10}, {11,14}, {16,19}, {17,20}, {15,21},
{ 0, 2}, { 1, 3}, { 7, 9}, { 6, 8}, {11,13}, {12,14}, {18,20}, {17,19}, {10,21},
{ 1, 2}, { 7, 8}, { 0, 6}, { 3, 9}, {12,13}, {18,19}, {11,17}, {14,20},
{ 0, 5}, { 1, 7}, { 2, 8}, { 4, 9}, {11,16}, {12,18}, {13,19}, {15,20},
{ 1, 6}, { 3, 8}, {12,17}, {14,19}, { 0,11}, { 9,20},
{ 1, 5}, { 4, 8}, { 3, 6}, {12,16}, {15,19}, {14,17}, {10,20},
{ 2, 5}, { 4, 7}, {13,16}, {15,18}, { 1,12}, { 8,19},
{ 4, 6}, { 3, 5}, {15,17}, {14,16}, { 1,11}, { 2,13}, { 7,18}, { 9,19},
{ 4, 5}, {15,16}, { 3,14}, { 2,11}, { 6,17}, {10,19},
{ 4,15}, { 3,13}, { 5,16}, { 7,17}, {10,18},
{ 4,14}, { 3,12}, { 6,16}, { 9,17},
{ 4,13}, { 3,11}, { 7,16}, {10,17},
{ 4,12}, { 8,16}, { 7,13},
{ 4,11}, { 9,16}, { 6,12}, { 8,14},
{10,16}, { 5,11}, { 7,12}, { 9,15},
{ 6,11}, {10,15}, { 9,14},
{ 7,11}, {10,14}, { 9,12},
{ 8,11}, {10,13},
{10,12}, { 9,11},
{10,11},
};
static const unsigned int network23[][2] = {
{ 0, 1}, { 3, 4}, { 6, 7}, { 9,10}, {12,13}, {15,16}, {18,19}, {21,22},
{ 2, 4}, { 5, 7}, { 8,10}, {11,13}, {14,16}, {17,19}, {20,22},
{ 2, 3}, { 1, 4}, { 5, 6}, { 8, 9}, { 7,10}, {11,12}, {14,15}, {13,16}, {17,18}, {20,21}, {19,22},
{ 0, 3}, { 5, 8}, { 6, 9}, { 4,10}, {11,14}, {12,15}, {17,20}, {18,21}, {16,22},
{ 0, 2}, { 1, 3}, { 7, 9}, { 6, 8}, {13,15}, {12,14}, {19,21}, {18,20}, {11,17}, {10,22},
{ 1, 2}, { 7, 8}, { 0, 6}, { 3, 9}, {13,14}, {19,20}, {12,18}, {15,21},
{ 0, 5}, { 1, 7}, { 2, 8}, { 4, 9}, {13,19}, {12,17}, {14,20}, {16,21},
{ 1, 6}, { 3, 8}, {13,18}, {15,20}, { 0,12}, { 9,21},
{ 1, 5}, { 4, 8}, { 3, 6}, {13,17}, {16,20}, {15,18}, { 0,11}, {10,21},
{ 2, 5}, { 4, 7}, {14,17}, {16,19}, { 1,13}, { 8,20},
{ 4, 6}, { 3, 5}, {16,18}, {15,17}, { 1,12}, { 2,14}, { 7,19}, { 9,20},
{ 4, 5}, {16,17}, { 1,11}, { 3,15}, { 6,18}, {10,20},
{ 4,16}, { 3,14}, { 2,11}, { 5,17}, { 7,18}, {10,19},
{ 4,15}, { 3,12}, { 6,17}, { 9,18},
{ 4,14}, { 3,11}, { 7,17}, {10,18},
{ 4,13}, { 8,17},
{ 4,12}, { 9,17}, { 7,13}, { 8,14},
{ 4,11}, {10,17}, { 6,12}, { 9,15},
{ 5,11}, { 7,12}, {10,16}, { 9,14},
{ 6,11}, {10,15}, { 9,12},
{ 7,11}, {10,14},
{ 8,11}, {10,13},
{10,12}, { 9,11},
{10,11},
};
static const unsigned int network24[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, {10,11}, {13,14}, {16,17}, {19,20}, {22,23},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {12,14}, {15,17}, {18,20}, {21,23},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, { 9,10}, { 8,11}, {12,13}, {15,16}, {14,17}, {18,19}, {21,22}, {20,23},
{ 0, 3}, { 1, 4}, { 6, 9}, { 7,10}, { 5,11}, {12,15}, {13,16}, {18,21}, {19,22}, {17,23},
{ 2, 4}, { 1, 3}, { 8,10}, { 7, 9}, { 0, 6}, {14,16}, {13,15}, {20,22}, {19,21}, {12,18}, {11,23},
{ 2, 3}, { 8, 9}, { 1, 7}, { 4,10}, {14,15}, {20,21}, {13,19}, {16,22}, { 0,12},
{ 2, 8}, { 1, 6}, { 3, 9}, { 5,10}, {14,20}, {13,18}, {15,21}, {17,22},
{ 2, 7}, { 4, 9}, {14,19}, {16,21}, { 1,13}, {10,22},
{ 2, 6}, { 5, 9}, { 4, 7}, {14,18}, {17,21}, {16,19}, { 1,12}, {11,22},
{ 3, 6}, { 5, 8}, {15,18}, {17,20}, { 2,14}, { 9,21},
{ 5, 7}, { 4, 6}, {17,19}, {16,18}, { 2,13}, { 3,15}, { 8,20}, {10,21},
{ 5, 6}, {17,18}, { 2,12}, { 4,16}, { 7,19}, {11,21},
{ 5,17}, { 4,15}, { 3,12}, { 6,18}, { 8,19}, {11,20},
{ 5,16}, { 4,13}, { 7,18}, {10,19},
{ 5,15}, { 4,12}, { 8,18}, {11,19},
{ 5,14}, { 9,18},
{ 5,13}, {10,18}, { 8,14}, { 9,15},
{ 5,12}, {11,18}, { 7,13}, {10,16},
{ 6,12}, { 8,13}, {11,17}, {10,15},
{ 7,12}, {11,16}, {10,13},
{ 8,12}, {11,15},
{ 9,12}, {11,14},
{11,13}, {10,12},
{11,12},
};
static const unsigned int network25[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, {10,11}, {13,14}, {16,17}, {19,20}, {21,22}, {23,24},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {12,14}, {15,17}, {18,20}, {21,23}, {22,24},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, { 9,10}, { 8,11}, {12,13}, {15,16}, {14,17}, {18,19}, {22,23}, {20,24},
{ 0, 3}, { 1, 4}, { 6, 9}, { 7,10}, { 5,11}, {12,15}, {13,16}, {18,22}, {19,23}, {17,24},
{ 2, 4}, { 1, 3}, { 8,10}, { 7, 9}, { 0, 6}, {14,16}, {13,15}, {18,21}, {20,23}, {11,24},
{ 2, 3}, { 8, 9}, { 1, 7}, { 4,10}, {14,15}, {19,21}, {20,22}, {16,23},
{ 2, 8}, { 1, 6}, { 3, 9}, { 5,10}, {20,21}, {12,19}, {15,22}, {17,23},
{ 2, 7}, { 4, 9}, {12,18}, {13,20}, {14,21}, {16,22}, {10,23},
{ 2, 6}, { 5, 9}, { 4, 7}, {14,20}, {13,18}, {17,22}, {11,23},
{ 3, 6}, { 5, 8}, {14,19}, {16,20}, {17,21}, { 0,13}, { 9,22},
{ 5, 7}, { 4, 6}, {14,18}, {15,19}, {17,20}, { 0,12}, { 8,21}, {10,22},
{ 5, 6}, {15,18}, {17,19}, { 1,14}, { 7,20}, {11,22},
{16,18}, { 2,15}, { 1,12}, { 6,19}, { 8,20}, {11,21},
{17,18}, { 2,14}, { 3,16}, { 7,19}, {10,20},
{ 2,13}, { 4,17}, { 5,18}, { 8,19}, {11,20},
{ 2,12}, { 5,17}, { 4,16}, { 3,13}, { 9,19},
{ 5,16}, { 3,12}, { 4,14}, {10,19},
{ 5,15}, { 4,12}, {11,19}, { 9,16}, {10,17},
{ 5,14}, { 8,15}, {11,18}, {10,16},
{ 5,13}, { 7,14}, {11,17},
{ 5,12}, { 6,13}, { 8,14}, {11,16},
{ 6,12}, { 8,13}, {10,14}, {11,15},
{ 7,12}, { 9,13}, {11,14},
{ 8,12}, {11,13},
{ 9,12},
{10,12},
{11,12},
};
static const unsigned int network26[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, { 9,10}, {11,12}, {14,15}, {17,18}, {20,21}, {22,23}, {24,25},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {10,12}, {13,15}, {16,18}, {19,21}, {22,24}, {23,25},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, {10,11}, { 8,12}, {13,14}, {16,17}, {15,18}, {19,20}, {23,24}, {21,25},
{ 0, 3}, { 1, 4}, { 6,10}, { 7,11}, { 5,12}, {13,16}, {14,17}, {19,23}, {20,24}, {18,25},
{ 2, 4}, { 1, 3}, { 6, 9}, { 8,11}, {15,17}, {14,16}, {19,22}, {21,24}, {12,25},
{ 2, 3}, { 7, 9}, { 8,10}, { 4,11}, {15,16}, {20,22}, {21,23}, {17,24},
{ 8, 9}, { 0, 7}, { 3,10}, { 5,11}, {21,22}, {13,20}, {16,23}, {18,24},
{ 0, 6}, { 1, 8}, { 2, 9}, { 4,10}, {13,19}, {14,21}, {15,22}, {17,23}, {11,24},
{ 2, 8}, { 1, 6}, { 5,10}, {15,21}, {14,19}, {18,23}, { 0,13}, {12,24},
{ 2, 7}, { 4, 8}, { 5, 9}, {15,20}, {17,21}, {18,22}, { 1,14}, {10,23},
{ 2, 6}, { 3, 7}, { 5, 8}, {15,19}, {16,20}, {18,21}, { 1,13}, { 9,22}, {12,23},
{ 3, 6}, { 5, 7}, {16,19}, {18,20}, { 2,15}, { 8,21}, {10,22},
{ 4, 6}, {17,19}, { 2,14}, { 3,16}, { 7,20}, {11,22},
{ 5, 6}, {18,19}, { 2,13}, { 4,17}, { 8,20}, {12,22}, {11,21},
{ 5,18}, { 4,16}, { 3,13}, { 6,19}, {10,20}, {12,21},
{ 5,17}, { 4,14}, { 7,19}, {12,20},
{ 5,16}, { 4,13}, { 8,19},
{ 5,15}, { 9,19},
{ 5,14}, {10,19}, { 8,15}, { 9,16},
{ 5,13}, {11,19}, { 7,14}, {10,17},
{12,19}, { 6,13}, { 8,14}, {10,16}, {11,18},
{ 7,13}, {12,18}, {11,16}, {10,14},
{ 8,13}, {12,17}, {11,15},
{12,16}, { 9,13},
{10,13}, {12,15},
{11,13}, {12,14},
{12,13},
};
static const unsigned int network27[][2] = {
{ 1, 2}, { 4, 5}, { 7, 8}, { 9,10}, {11,12}, {14,15}, {16,17}, {18,19}, {21,22}, {23,24}, {25,26},
{ 0, 2}, { 3, 5}, { 6, 8}, { 9,11}, {10,12}, {13,15}, {16,18}, {17,19}, {20,22}, {23,25}, {24,26},
{ 0, 1}, { 3, 4}, { 2, 5}, { 6, 7}, {10,11}, { 8,12}, {13,14}, {17,18}, {15,19}, {20,21}, {24,25}, {22,26},
{ 0, 3}, { 1, 4}, { 6,10}, { 7,11}, { 5,12}, {13,17}, {14,18}, {20,24}, {21,25}, {19,26},
{ 2, 4}, { 1, 3}, { 6, 9}, { 8,11}, {13,16}, {15,18}, {20,23}, {22,25}, {12,26},
{ 2, 3}, { 7, 9}, { 8,10}, { 4,11}, {14,16}, {15,17}, {21,23}, {22,24}, {13,20}, {18,25},
{ 8, 9}, { 0, 7}, { 3,10}, { 5,11}, {15,16}, {22,23}, {14,21}, {17,24}, {19,25},
{ 0, 6}, { 1, 8}, { 2, 9}, { 4,10}, {15,22}, {14,20}, {16,23}, {19,24}, {11,25},
{ 2, 8}, { 1, 6}, { 5,10}, {15,21}, {17,23}, { 0,14}, {12,25},
{ 2, 7}, { 4, 8}, { 5, 9}, {15,20}, {18,23}, {17,21}, { 0,13}, {10,24},
{ 2, 6}, { 3, 7}, { 5, 8}, {19,23}, {16,20}, {18,22}, { 1,15}, {12,24},
{ 3, 6}, { 5, 7}, {17,20}, {19,22}, { 2,16}, { 1,13}, { 9,23},
{ 4, 6}, {18,20}, {19,21}, { 2,15}, { 3,17}, { 8,22}, {10,23},
{ 5, 6}, {19,20}, { 2,14}, { 4,18}, { 7,21}, {11,23},
{ 2,13}, { 5,19}, { 4,17}, { 3,14}, { 6,20}, { 8,21}, {12,23}, {11,22},
{ 5,18}, { 3,13}, { 4,15}, { 7,20}, {10,21}, {12,22},
{ 5,17}, { 4,13}, { 8,20}, {12,21},
{ 5,16}, { 9,20},
{ 5,15}, {10,20}, { 9,16},
{ 5,14}, {11,20}, { 8,15}, {10,17},
{ 5,13}, {12,20}, { 7,14}, {10,16}, {11,18},
{ 6,13}, { 8,14}, {12,19}, {11,16},
{ 7,13}, {12,18}, {10,14}, {11,15},
{ 8,13}, {12,17},
{12,16}, { 9,13},
{10,13}, {12,15},
{11,13}, {12,14},
{12,13},
};
static const unsigned int network28[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {12,13}, {15,16}, {17,18}, {19,20}, {22,23}, {24,25}, {26,27},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, {10,12}, {11,13}, {14,16}, {17,19}, {18,20}, {21,23}, {24,26}, {25,27},
{ 0, 1}, { 4, 5}, { 2, 6}, { 7, 8}, {11,12}, { 9,13}, {14,15}, {18,19}, {16,20}, {21,22}, {25,26}, {23,27},
{ 0, 4}, { 1, 5}, { 7,11}, { 8,12}, { 6,13}, {14,18}, {15,19}, {21,25}, {22,26}, {20,27},
{ 0, 3}, { 2, 5}, { 7,10}, { 9,12}, {14,17}, {16,19}, {21,24}, {23,26}, {13,27},
{ 1, 3}, { 2, 4}, { 8,10}, { 9,11}, { 0, 7}, { 5,12}, {15,17}, {16,18}, {22,24}, {23,25}, {14,21}, {19,26},
{ 2, 3}, { 9,10}, { 1, 8}, { 4,11}, { 6,12}, {16,17}, {23,24}, {15,22}, {18,25}, {20,26}, { 0,14},
{ 2, 9}, { 1, 7}, { 3,10}, { 6,11}, {16,23}, {15,21}, {17,24}, {20,25}, {12,26},
{ 2, 8}, { 4,10}, {16,22}, {18,24}, { 1,15}, {11,25}, {13,26},
{ 2, 7}, { 5,10}, { 4, 8}, {16,21}, {19,24}, {18,22}, { 1,14}, {13,25},
{ 6,10}, { 3, 7}, { 5, 9}, {20,24}, {17,21}, {19,23}, { 2,16},
{ 4, 7}, { 6, 9}, {18,21}, {20,23}, { 2,15}, { 3,17}, {10,24},
{ 5, 7}, { 6, 8}, {19,21}, {20,22}, { 2,14}, { 4,18}, { 9,23}, {11,24},
{ 6, 7}, {20,21}, { 4,17}, { 5,19}, { 3,14}, { 8,22}, {12,24},
{ 6,20}, { 5,17}, { 4,15}, { 7,21}, { 9,22}, {13,24}, {12,23},
{ 6,19}, { 4,14}, { 5,16}, { 8,21}, {11,22}, {13,23},
{ 6,18}, { 5,14}, { 9,21}, {13,22},
{ 6,17}, {10,21},
{ 6,16}, {11,21}, {10,17},
{ 6,15}, {12,21}, { 9,16}, {11,18},
{ 6,14}, {13,21}, { 8,15}, {11,17}, {12,19},
{ 7,14}, { 9,15}, {13,20}, {12,17},
{ 8,14}, {13,19}, {11,15}, {12,16},
{ 9,14}, {13,18},
{13,17}, {10,14},
{11,14}, {13,16},
{12,14}, {13,15},
{13,14},
};
static const unsigned int network29[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 8, 9}, {10,11}, {12,13}, {15,16}, {17,18}, {19,20}, {21,22}, {23,24}, {25,26}, {27,28},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, {10,12}, {11,13}, {14,16}, {17,19}, {18,20}, {21,23}, {22,24}, {25,27}, {26,28},
{ 0, 1}, { 4, 5}, { 2, 6}, { 7, 8}, {11,12}, { 9,13}, {14,15}, {18,19}, {16,20}, {22,23}, {26,27}, {21,25}, {24,28},
{ 0, 4}, { 1, 5}, { 7,11}, { 8,12}, { 6,13}, {14,18}, {15,19}, {22,26}, {23,27}, {20,28},
{ 0, 3}, { 2, 5}, { 7,10}, { 9,12}, {14,17}, {16,19}, {22,25}, {24,27}, {13,28},
{ 1, 3}, { 2, 4}, { 8,10}, { 9,11}, { 0, 7}, { 5,12}, {15,17}, {16,18}, {23,25}, {24,26}, {14,22}, {19,27},
{ 2, 3}, { 9,10}, { 1, 8}, { 4,11}, { 6,12}, {16,17}, {24,25}, {14,21}, {15,23}, {18,26}, {20,27},
{ 2, 9}, { 1, 7}, { 3,10}, { 6,11}, {16,24}, {15,21}, {17,25}, {20,26}, {12,27},
{ 2, 8}, { 4,10}, {16,23}, {18,25}, { 0,15}, {11,26}, {13,27},
{ 2, 7}, { 5,10}, { 4, 8}, {16,22}, {19,25}, { 0,14}, {13,26},
{ 6,10}, { 3, 7}, { 5, 9}, {16,21}, {20,25}, {18,22}, {19,23},
{ 4, 7}, { 6, 9}, {17,21}, {20,24}, { 1,16}, {10,25},
{ 5, 7}, { 6, 8}, {18,21}, {20,23}, { 2,17}, { 1,14}, { 9,24}, {11,25},
{ 6, 7}, {19,21}, {20,22}, { 2,16}, { 3,18}, { 8,23}, {12,25},
{20,21}, { 2,15}, { 4,19}, { 7,22}, { 9,23}, {13,25}, {12,24},
{ 2,14}, { 4,18}, { 5,20}, { 6,21}, { 8,22}, {11,23}, {13,24},
{ 6,20}, { 5,18}, { 3,14}, { 4,15}, { 9,22}, {13,23},
{ 6,19}, { 4,14}, { 5,16}, {10,22},
{ 6,18}, { 5,14}, {11,22},
{ 6,17}, {12,22}, {10,18}, {11,19},
{ 6,16}, {13,22}, { 9,17}, {11,18}, {12,20},
{ 6,15}, { 8,16}, {13,21}, {12,18},
{ 6,14}, { 7,15}, { 9,16}, {13,20},
{ 7,14}, { 9,15}, {13,19}, {12,16},
{ 8,14}, {13,18}, {11,15},
{ 9,14}, {13,17},
{10,14}, {13,16},
{11,14}, {13,15},
{12,14},
{13,14},
};
static const unsigned int network30[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12}, {13,14}, {16,17}, {18,19}, {20,21}, {22,23}, {24,25}, {26,27}, {28,29},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, { 8,10}, {11,13}, {12,14}, {15,17}, {18,20}, {19,21}, {22,24}, {23,25}, {26,28}, {27,29},
{ 0, 1}, { 4, 5}, { 2, 6}, { 8, 9}, {12,13}, { 7,11}, {10,14}, {15,16}, {19,20}, {17,21}, {23,24}, {27,28}, {22,26}, {25,29},
{ 0, 4}, { 1, 5}, { 8,12}, { 9,13}, { 6,14}, {15,19}, {16,20}, {23,27}, {24,28}, {21,29},
{ 0, 3}, { 2, 5}, { 8,11}, {10,13}, {15,18}, {17,20}, {23,26}, {25,28}, {14,29},
{ 1, 3}, { 2, 4}, { 9,11}, {10,12}, { 0, 8}, { 5,13}, {16,18}, {17,19}, {24,26}, {25,27}, {15,23}, {20,28},
{ 2, 3}, {10,11}, { 0, 7}, { 1, 9}, { 4,12}, { 6,13}, {17,18}, {25,26}, {15,22}, {16,24}, {19,27}, {21,28},
{ 2,10}, { 1, 7}, { 3,11}, { 6,12}, {17,25}, {16,22}, {18,26}, {21,27}, { 0,15}, {13,28},
{ 2, 9}, { 4,11}, {17,24}, {19,26}, { 1,16}, {12,27}, {14,28},
{ 2, 8}, { 5,11}, {17,23}, {20,26}, { 1,15}, {14,27},
{ 2, 7}, { 6,11}, { 4, 8}, { 5, 9}, {17,22}, {21,26}, {19,23}, {20,24},
{ 3, 7}, { 6,10}, {18,22}, {21,25}, { 2,17}, {11,26},
{ 4, 7}, { 6, 9}, {19,22}, {21,24}, { 2,16}, { 3,18}, {10,25}, {12,26},
{ 5, 7}, { 6, 8}, {20,22}, {21,23}, { 2,15}, { 4,19}, { 9,24}, {13,26},
{ 6, 7}, {21,22}, { 4,18}, { 5,20}, { 3,15}, { 8,23}, {10,24}, {14,26},
{ 6,21}, { 5,18}, { 4,16}, { 7,22}, {10,23}, {13,24}, {14,25},
{ 6,20}, { 4,15}, { 5,17}, { 8,22}, {12,23}, {14,24},
{ 6,19}, { 5,15}, { 9,22}, {14,23},
{ 6,18}, {10,22},
{ 6,17}, {11,22}, {10,18},
{ 6,16}, {12,22}, { 9,17}, {11,19},
{ 6,15}, {13,22}, { 8,16}, {10,17}, {12,20},
{14,22}, { 7,15}, {10,16}, {12,19}, {13,21},
{ 8,15}, {14,21}, {13,19}, {12,16},
{ 9,15}, {14,20}, {13,17},
{10,15}, {14,19},
{11,15}, {14,18},
{12,15}, {14,17},
{13,15}, {14,16},
{14,15},
};
static const unsigned int network31[][2] = {
{ 1, 2}, { 3, 4}, { 5, 6}, { 7, 8}, { 9,10}, {11,12}, {13,14}, {15,16}, {17,18}, {19,20}, {21,22}, {23,24}, {25,26}, {27,28}, {29,30},
{ 0, 2}, { 3, 5}, { 4, 6}, { 7, 9}, { 8,10}, {11,13}, {12,14}, {15,17}, {16,18}, {19,21}, {20,22}, {23,25}, {24,26}, {27,29}, {28,30},
{ 0, 1}, { 4, 5}, { 2, 6}, { 8, 9}, {12,13}, { 7,11}, {10,14}, {16,17}, {20,21}, {15,19}, {18,22}, {24,25}, {28,29}, {23,27}, {26,30},
{ 0, 4}, { 1, 5}, { 8,12}, { 9,13}, { 6,14}, {16,20}, {17,21}, {24,28}, {25,29}, {15,23}, {22,30},
{ 0, 3}, { 2, 5}, { 8,11}, {10,13}, {16,19}, {18,21}, {24,27}, {26,29}, {14,30},
{ 1, 3}, { 2, 4}, { 9,11}, {10,12}, { 0, 8}, { 5,13}, {17,19}, {18,20}, {25,27}, {26,28}, {16,24}, {21,29},
{ 2, 3}, {10,11}, { 0, 7}, { 1, 9}, { 4,12}, { 6,13}, {18,19}, {26,27}, {16,23}, {17,25}, {20,28}, {22,29},
{ 2,10}, { 1, 7}, { 3,11}, { 6,12}, {18,26}, {17,23}, {19,27}, {22,28}, { 0,16}, {13,29},
{ 2, 9}, { 4,11}, {18,25}, {20,27}, { 0,15}, { 1,17}, {12,28}, {14,29},
{ 2, 8}, { 5,11}, {18,24}, {21,27}, { 1,15}, {14,28},
{ 2, 7}, { 6,11}, { 4, 8}, { 5, 9}, {18,23}, {22,27}, {20,24}, {21,25},
{ 3, 7}, { 6,10}, {19,23}, {22,26}, { 2,18}, {11,27},
{ 4, 7}, { 6, 9}, {20,23}, {22,25}, { 2,17}, { 3,19}, {10,26}, {12,27},
{ 5, 7}, { 6, 8}, {21,23}, {22,24}, { 2,16}, { 4,20}, { 9,25}, {13,27},
{ 6, 7}, {22,23}, { 2,15}, { 4,19}, { 5,21}, { 8,24}, {10,25}, {14,27},
{ 6,22}, { 5,19}, { 3,15}, { 4,16}, { 7,23}, {10,24}, {13,25}, {14,26},
{ 6,21}, { 4,15}, { 5,17}, { 8,23}, {12,24}, {14,25},
{ 6,20}, { 5,15}, { 9,23}, {14,24},
{ 6,19}, {10,23},
{ 6,18}, {11,23},
{ 6,17}, {12,23}, {10,18}, {11,19},
{ 6,16}, {13,23}, { 9,17}, {12,20},
{ 6,15}, {14,23}, { 8,16}, {10,17}, {12,19}, {13,21},
{ 7,15}, {10,16}, {14,22}, {13,19},
{ 8,15}, {14,21}, {12,16}, {13,17},
{ 9,15}, {14,20},
{10,15}, {14,19},
{11,15}, {14,18},
{12,15}, {14,17},
{13,15}, {14,16},
{14,15},
};
static const unsigned int network32[][2] = {
{ 0, 1}, { 2, 3}, { 4, 5}, { 6, 7}, { 8, 9}, {10,11}, {12,13}, {14,15}, {16,17}, {18,19}, {20,21}, {22,23}, {24,25}, {26,27}, {28,29}, {30,31},
{ 0, 2}, { 1, 3}, { 4, 6}, { 5, 7}, { 8,10}, { 9,11}, {12,14}, {13,15}, {16,18}, {17,19}, {20,22}, {21,23}, {24,26}, {25,27}, {28,30}, {29,31},
{ 1, 2}, { 5, 6}, { 0, 4}, { 3, 7}, { 9,10}, {13,14}, { 8,12}, {11,15}, {17,18}, {21,22}, {16,20}, {19,23}, {25,26}, {29,30}, {24,28}, {27,31},
{ 1, 5}, { 2, 6}, { 9,13}, {10,14}, { 0, 8}, { 7,15}, {17,21}, {18,22}, {25,29}, {26,30}, {16,24}, {23,31},
{ 1, 4}, { 3, 6}, { 9,12}, {11,14}, {17,20}, {19,22}, {25,28}, {27,30}, { 0,16}, {15,31},
{ 2, 4}, { 3, 5}, {10,12}, {11,13}, { 1, 9}, { 6,14}, {18,20}, {19,21}, {26,28}, {27,29}, {17,25}, {22,30},
{ 3, 4}, {11,12}, { 1, 8}, { 2,10}, { 5,13}, { 7,14}, {19,20}, {27,28}, {17,24}, {18,26}, {21,29}, {23,30},
{ 3,11}, { 2, 8}, { 4,12}, { 7,13}, {19,27}, {18,24}, {20,28}, {23,29}, { 1,17}, {14,30},
{ 3,10}, { 5,12}, {19,26}, {21,28}, { 1,16}, { 2,18}, {13,29}, {15,30},
{ 3, 9}, { 6,12}, {19,25}, {22,28}, { 2,16}, {15,29},
{ 3, 8}, { 7,12}, { 5, 9}, { 6,10}, {19,24}, {23,28}, {21,25}, {22,26},
{ 4, 8}, { 7,11}, {20,24}, {23,27}, { 3,19}, {12,28},
{ 5, 8}, { 7,10}, {21,24}, {23,26}, { 3,18}, { 4,20}, {11,27}, {13,28},
{ 6, 8}, { 7, 9}, {22,24}, {23,25}, { 3,17}, { 5,21}, {10,26}, {14,28},
{ 7, 8}, {23,24}, { 3,16}, { 5,20}, { 6,22}, { 9,25}, {11,26}, {15,28},
{ 7,23}, { 6,20}, { 4,16}, { 5,17}, { 8,24}, {11,25}, {14,26}, {15,27},
{ 7,22}, { 5,16}, { 6,18}, { 9,24}, {13,25}, {15,26},
{ 7,21}, { 6,16}, {10,24}, {15,25},
{ 7,20}, {11,24},
{ 7,19}, {12,24},
{ 7,18}, {13,24}, {11,19}, {12,20},
{ 7,17}, {14,24}, {10,18}, {13,21},
{ 7,16}, {15,24}, { 9,17}, {11,18}, {13,20}, {14,22},
{ 8,16}, {11,17}, {15,23}, {14,20},
{ 9,16}, {15,22}, {13,17}, {14,18},
{10,16}, {15,21},
{11,16}, {15,20},
{12,16}, {15,19},
{13,16}, {15,18},
{14,16}, {15,17},
{15,16},
};

typedef struct {
const unsigned int comparators;
const unsigned int (*pNetwork)[2];
} Network;

#define elemof(ary) (sizeof(ary)/sizeof(ary[0]))
#define NETWORK(n) {elemof(network##n), network##n}

static const Network networks[] = {
{0, NULL},
{0, NULL},
NETWORK(02),
NETWORK(03),
NETWORK(04),
NETWORK(05),
NETWORK(06),
NETWORK(07),
NETWORK(08),
NETWORK(09),
NETWORK(10),
NETWORK(11),
NETWORK(12),
NETWORK(13),
NETWORK(14),
NETWORK(15),
NETWORK(16),
NETWORK(17),
NETWORK(18),
NETWORK(19),
NETWORK(20),
NETWORK(21),
NETWORK(22),
NETWORK(23),
NETWORK(24),
NETWORK(25),
NETWORK(26),
NETWORK(27),
NETWORK(28),
NETWORK(29),
NETWORK(30),
NETWORK(31),
NETWORK(32),
};
#undef NETWORK

static const size_t cutoff = elemof(networks);

template<typename Elem>
inline void networkSort(Elem *p, size_t n) {
const unsigned int (* pNetwork)[2], (* pEnd)[2];
Elem *p0, *p1;
assert(n < elemof(networks));
pNetwork = networks[n].pNetwork;
pEnd = pNetwork + networks[n].comparators;
for(; pNetwork < pEnd; pNetwork++) {
p0 = p + (*pNetwork)[0];
p1 = p + (*pNetwork)[1];
if(*p1 < *p0) swap(p0, p1);
}
}

January 18th, 2011 | 荒唐 | Categories: 数学, 算法 | Comments: No Comments

号称世界上最难的逻辑题

已知：
1.神无所不知只说真话，鬼无所不知只说假话，人有所不知胡乱说话，除此之外三者没有任何区别。他们一定回答且只能回答任何有确定答案的是非题。
2.“Da”和“Ja”一个永远代表“是”另一个永远代表“否”，但你完全不知道二者分别代表哪个。

问题Z：你面前站着神、鬼、人各一，你不知道三者分别是谁，你必须通过提问正确区分出三者。你每次只能对其中一个提问，一共只能问三次，但你每次提问得到的回答只能是“Da”或“Ja”。

如果你觉得Z太难，这里有一个简化版Z’：跟Z类似，但得到的答案只能是“是”或“否”。

如果你还是觉得太难，还有一个更简单的问题Y：你面前有两条路，一条通向天堂，一条通向地狱。路口站着神、鬼各一，你不知道二者分别是谁。你现在只能对其中一个提出一个是非题，判断出哪条路通向天堂。但你提问得到的回答只会是“Da”或“Ja”。

如果你觉得Y也太难，也可以简化为Y’：跟Y类似，但得到的答案只会是“是”或“否”。

附加条件：
如果你解决了Z或Z’，那么请加一个条件：你对其中一个问的问题中不允许同时提及另外两个。
如果你解决了Y或Y’，那么请加一个条件：你对其中一个问的问题中不允许提及另外一个。

问题Y还可以有如下变体Y”：路口只站着一个家伙，你只知道他要么是神要么是鬼。你现在只能向他问一个是非题，判断出哪条路通向天堂。其他不变。

一点提示：
对A提问：『将鬼、人、神分别编号为1，2，3，那么请问B的编号大于C么？』
对A提问：『如果我问你『B是乱说话的人么？』，你会回答什么？』
对任何一个提问：请问『……』这个问题的答案是Da么？

January 17th, 2011 | 荒唐 | Categories: 数学 | Comments: No Comments

二元关系学习总结

preorder（预序）: reflexive, transitive

partial order（偏序，对应图论的有向无环图）: preorder + anti-symmetric
total preorder（完全预序）: preorder + total
equivalence（等价）: preorder + symmetric

complete（全互连，对应图论的完全连通图）: total preorder + symmetric or equivalence + total
equality（相等）: equivalence + anti-symmetric or partial order + symmetic
total order（全序）: partial order + total or total preorder + anti-symmetric

(total order, AKA linear order, simple order, or (non-strict) ordering)
注意，上述关系中的后三个关系所用到的某些属性已经不是独立的了，例如相等关系用自反性、对称性、反对称性就可以导出传递性（因为对称性和反对称性限制了关系只能发生在每个元素自身上，自反性则保证了每个元素自身都满足这个关系。结果没有可能发生传递，因此传递性自然被满足。）

上面的提到的各种关系R所用到的各种属性：
reflexive（自反性）: for all x in X it holds that xRx
transitive（传递性）: for all x, y and z in X it holds that if xRy and yRz then xRz.
symmetric（对称性）: for all x and y in X it holds that if xRy then yRx
anti-symmetric（反对称性）: for all x and y in X it holds that if xRy and yRx then x = y
total（完全性）: for all x and y in X it holds that xRy or yRx (or both)

二元关系的其它一些常见属性：
irreflexive（非自反性）: for all x in X it holds that not xRx
coreflexive（伴自反性）: for all x and y in X it holds that if xRy then x = y
asymmetric（非对称性）: for all x and y in X it holds that if xRy then not yRx

1
2
3
4
5
6
7
8
9
10
11

PR
/|\
/ | \
/ | \
/ | \
PA TP EV
|\ /\ /|
| \/ \/ |
| /\ /\ |
|/ \/ \|
TO EQ CP

PR: preorder
PA: partial order
TP: total preorder
EV: equivalence
TO: total order
EQ: equality
CP: complete connection

/: anti-symmetric
|: total
\: symmetric

一个重要的未讨论过的关系：

well order（良序）: total order + well-founded

well-founded（良基关系）：every non-empty subset of X has a minimal element with respect to R; that is, for every non-empty subset S of X, there is an element m of S such that for every element s≠m of S, the pair (s,m) is not in R.

If a set is totally ordered, then the following are equivalent:
1. The set is well-ordered. That is, every nonempty subset has a least element.
2. Transfinite induction works for the entire ordered set.
3. Every strictly decreasing sequence of elements of the set must terminate after only finitely many steps (assuming the axiom of dependent choice).

其它关系：
* Dependency relation, a symmetric, reflexive relation.
* Independency relation, a symmetric, irreflexive relation.
这两种关系是互补的。

January 17th, 2011 | 荒唐 | Categories: 数学 | Comments: No Comments

图灵机vs数学家——图灵机计算能力的分析

（这是我2009年5月在繁星客栈上发表的，现稍加修改放在这里）

这里我尝试回答三个问题
0.是否存在数学家可以做出判定的问题，不存在判定该问题的图灵机？
1.是否存在这样的通用判定图灵机，输入任何数学家可以判定的问题，该图灵机都能在有限步骤之内输出其判定结果，而不输出任何错误的判定结果？
2.是否存在这样的自动判定图灵机，自动尝试判定所有可能的判定问题，而对于其中任何一个数学家可以判定的问题，该图灵机都可以在有限步骤之内输出其判定结果，而不输出任何错误的判定结果？

现在我们对数学家做一个假定：只有能够完全形式化的有限判定过程，才会被数学家承认。
这个假定是合理的，虽然天才的数学家可以用直觉、灵感、做梦、神启等等各种惊人的手段获得一个问题判定结果，但只有能够被彻底形式化的有限判定过程才会被认为是可靠的判定过程。换言之，任何一个能够被数学家认可的判定过程，绝对不能包含任何直觉成分。

上述假定蕴含这样一个结果：
能被数学家承认的任何判定，其步骤数目必然有限。
能被数学家判定的任何问题，其符号刻画必然有限。

有限符号可刻画的问题的全集显然是递归可枚举集，因为它是所有有限长字符串集合的子集，因此可以用自然数i进行编号，记为Pi。
同理，刻画任何有效判定过程的符号串长度必然有限，因此显然是递归可枚举集，也可以用自然数j进行编号，记为Dj。
任何形式系统的推理规则，至多属于乔姆斯基无限制文法的子集，因此推理规则所生成的语言必然是递归可枚举语言的子集，而递归可枚举语言是图灵机可接受（但未必可判定）语言。所有形式系统的推理规则，都可以用自然数k进行编号，记为Lk。

判定【Dj是否为Lk的问题Pi的有效判定过程】，可以用一个通用验证图灵机V(Lk,Pi,Dj)进行判定，而且这是个可判定过程。因为Lk中任何一个判定过程中的任何一个步骤否有效，可以直接套用Lk的推理规则进行判定，而由于整个判定过程的步骤必然有限，因此整个判定过程Dj的有效性必然是可以被图灵机V判定的。

现在我们来构造一个图灵机H(Lk,Pi)，对于给定的形式系统Lk以及Lk的问题Pi，如果Lk中存在对Pi的有效判定过程Dj，那么图灵机H就输出Pi在Lk内的判定结果。但如果Lk中不存在对Pi的有效判定，H永不停机。

为了构造H，我们先考虑一个不可行的构造，然后将其改造为可行的构造：
构造无穷多图灵机Hj(Lk,Pi)，其定义为V(Lk,Pi,Dj)。显然，如果存在某个j，Dj是Pi在Lk下的有效判定，那么Hj必然在有限步骤内停机。
如果将所有的Hj同时启动，那么只要问题Pi在Lk下可判定，那么至少有一个Hj会在有限时间内输出判定，除非问题Pj在Lk下不可判定。

但是上述机构造需要同时运行无数个图灵机，是不可接受的。不过很容易将上述改造为可接受的构造：
构造H(Lk,Pi)，H包含一个循环，在第j次循环中，H先枚举出图灵机Hj的仿真程序，然后将已经枚举出的图灵机H0-Hj的仿真程序分别单步执行一步。显然，H的任何一次循环都必然在有限步骤内结束，只不过越往后循环周期越长。这样，只要Pi在Lk内可判定，那么必然存在某个Hj在运行m个步骤后停机给出判定结果，那么H(Lk,Pi)就必然在第j+m个循环之内停机。反之，如果Pi在Lk内不可判定，那么H永远也不停机。

于是，H就是符合前述要求的图灵机。

现在，我们要利用H(Lk,Pi,Dk)来构造一个永不停机的图灵机X，X不接受任何输入，但X对于任何一个形式系统Lk中任何一个可判定问题Pi，都可以在有限时间内输出其判定结果（连同Lk和Pi的编号一起输出），而对于任何一个不可判定的问题，X都永远不给出对该问题的任何输出。

类似于构造H的过程，我们先考虑一个不可行的构造，然后改造为可行的构造：
二元组(Lk,Pi)显然是一个递归可枚举集，因此可以用自然数n进行编号：n=f(Lk,Pi)，(Lk,Pi)=g(n)，f和g互为反函数。
构造无穷多图灵机Xn，其定义为：如果H(g(n))停机输出判定结果d，Xn就输出(n,d)。显然，只要Pi在Lk中可判定，Xn就必然在有限步骤内停机并输出(n,d)，反之Xn永不停机。
如果将所有的Xn同时启动，那么任何Lk中的任何可判定问题Pi，都必然在有限步骤内被某个Xn输出，输出内容为(n,d)，其中n=f(Lk,Pi)。

上述构造当然也是不可接受的，我们仿照改造H的方法改造X
构造图灵机X，X包含一个循环，在第n次循环中，X先枚举出图灵机Xn的仿真程序，然后将已经枚举出的图灵机X0-Xn的仿真程序分别单步执行一步。显然，X的任何一次循环都必然在有限步骤内结束，只不过越往后循环周期越长。这样，对于任何Lk中的任何Pi，只要Pi在Lk中是可判定的且判定结果为d，那么Xn（n=f(Lk,Pi)）必然在某个有限步骤s处停机并输(n,d)，而Xn的第s步必然在X的第n+s个循环中被执行到，X必然在n+s个循环之内，输出(n,d)。对于任何形式系统中的任何不可判定的问题，X永远都不会输出判定结果。

于是，X就是符合前述要求的图灵机。

现在澄清几件事情：
1.H和X都不会对任何形式系统中的任何不可判定问题给出判定。
2.对于任何Lk中的任何【Pi】，无论【Pi】在Lk中是否可判定，都存在整数i’，使得【Pi’】==【Pi在Lk中可判定】，因此【Pi在Lk中可判定】这个问题迟早会被X枚举出来并尝试对之进行判定。只要【Pi在Lk中可判定】在某个形式系统Lk’中可判定，那么【Pi在Lk中可判定】的判定结果必然会在有限步骤内被X输出。
3.X在枚举Xn的过程中，许多Xn是根本不会停机的，而每次循环中X都必须单步执行所有尚未停机的Xn，因此X的效率会越来越低。但正如我们前面所讨论的，只要一个问题可以判定，X必然会在有限步骤内输出这个问题的判定，X的能力不会随着效率越来越低而变弱。如果实在觉得这种垃圾越来越多的系统很不舒服，那么还存在这样一个优化：每当某个Xn停机输出了某个问题A的判定结果，就检查A的内容是不是在断言另一个问题B不可判定，如果A有效断言出B不可判定，那么就将正在尝试判定B的图灵机从循环中删除。甚至还可以对B做个标记，在枚举新问题的时候，凡是将问题B作为子问题的问题，都将被直接跳过。不过这些优化其实没什么意义，我们的目的仅仅是讨论图灵机的计算能力，并不关心性能。

——————————————————————————————
现在说一点题外话，数学上明明允许图灵机不可判定的问题存在，也允许超越图灵机的计算模型存在，而我们仅仅对数学家做了一个简单的限制，数学家的计算能力就被限制成不超越图灵机了呢？

这个问题很简单。我们所说的形式系统当然都是有限刻画的。数学家可以谈论某些必须由无限符号才能刻画的数学系统的存在性，甚至谈论这些系统的某些能力和限制，但完全无法使用这些系统进行推理。我们之所以可以谈论这些系统的某些能力和限制，是因为精确分析这些东西仅仅需要有限符号。于是，图灵机也一样可以给出关于这些系统的某些有限符号就可以刻画的属性的判定结果。

事实上，即便是我们熟悉的实数集，其中属性能够被有限符号所精确刻画的实数（也包括π、e、γ等）也只是实数集的一个可数子集。

除非数学家可以分辨出连续统那么多不同的符号甚至更多，以至于整个实数轴的每一个实数对于数学家来说一目了然，那么数学家也就具备了Hyper Computing的能力，我在文章开头对数学家所做的假设也就不再成立了。但这种情况下，数学家所能够提出的机械计算模型肯定要比图灵机更强。这种数学家的本事简直赶上上帝了，我们有能力回答的一切数学问题，对于这种超级数学家来说都可以一眼看出答案。

January 17th, 2011 | 荒唐 | Categories: 哲学, 数学, 算法 | Comments: 2 Comments

暴力冲突——草稿

付诸实施的暴力往往意味着至少一方在赌博。
人通常不会对自己完全清楚的决无胜算的对手进行暴力反抗。比方说遇到山崩地裂，除了脑子进水的，没人会去对抗。

一般来说只有在双方都认为实施暴力有利于自己的情况下，才会发生暴力冲突。

此处要澄清一个误解：实力明显弱的一方有时明知会失败却也要暴力对抗强者，但这并不是反例。因为强者很可能并不完全了解弱者的实力，虽然占绝对优势，但如果强者知道弱者会尽力抵抗，仍然会对策略进行调整，从而导致对弱者有利的最终结果。如果双方都从一开始就知道双方的实力对比，而且双方都知道对方了解自己，弱者却仍然要暴力对抗强者，就说明弱者对暴力本身的有强烈偏好，或者对最大程度损害对手利益有强烈偏好，比方说那些电影里经常出现的为荣誉而战的战斗狂。这种情况下对于这种战斗狂来说实施暴力符合自己的偏好（有利），即便根本得不到其他的回报。

在上述意义上，当利益冲突的双方没有其它便宜的渠道获得对方实力信息，而又都认为暴力冲突有利于己方，就很可能实施暴力对抗。换言之，暴力对抗提供了一条了解对方实力信息的虽然血腥但却非常直接的途径。

当然，由于存在许多不可控因素，即便是实力上占优势的一方也未必一定能够在冲突中取得胜利，因此冲突往往带有赌博性质。弱势一方即便知道自己弱势，但又认为自己不是完全没有希望获胜，失败或者投降的结果对自己的偏好来说相差不多，那么弱势一方就很可能会暴力对抗强者。

————————————————————————
社会规则能够取代直接付诸实施的暴力产生效果仅仅是因为所有人都知道存在一个强大的未付诸实施的暴力（或者叫施暴的能力）做规则的保障。核威慑不但没有让世界变成核辐射地狱，反而带来了长时间的相对和平，这本身也是因为各参与方都非常清楚地知道别人手中握有巨大的施暴能力。当然这种核威慑下的和平到底能有多可靠就不是那么容易判断了，取决于许多细节因素。

有人用公司总裁作为例子来说明总裁权力的来源是股东的授权而并非来源于暴力。但如果没有背后的国家机器的暴力保障，总裁和股东手里的权力还存在么？总裁当然不需要直接施暴来执行自己的决策，总裁握有施暴的能力。只要总裁的行为是受法律保护的行为，那么在迫不得已必须通过暴力解决问题的时候，法律暴力就会站在总裁一边。正因为这种威慑，所以总裁通常根本不必真的施暴就可以迫使员工执行自己的决策。同样，只要法律不是专门为总裁服务的，那么如果员工的行为是受法律保护的，员工在自身行为合法的条件下也具有这种暴力威慑，于是总裁就不敢随便以非法的手段处置员工。

不要说人类，就连动物都是如此，握有施暴的能力，并且让对手知道自己有这种能力，那么通常就用不着真正施暴。一头狮子和一只鬣狗都要到小水洼里喝水，难道狮子还真得把鬣狗杀了才能安心喝水么？暴力最终付诸实施是因为双方在施暴之前都认为施暴所导致的后果更符合自己的意愿，有时这是因为弱势一方很不了解敌我实力对比，有时这是因为弱势一方认为投降比战败的结果更差。

January 11th, 2011 | 荒唐 | Categories: 哲学 | Comments: No Comments

相对论König定理的简单证明

König定理：质点组的总动能等于质心动能加上所有质点相对于质心的动能。
（这里我们不用『质点系』而用『质点组』，以免跟『质心系』『参考系』的『系』字混淆）
以前看到过一种相对论情况下的证明，反复使用速度变换公式，很繁琐。其实利用总能量、动能、质量的关系，在相对论中该定理的证明比经典力学容易得多。
以下约定在该质点组的质心系中的所有物理量都使用上标 $c$ 。注意，质点组的质心系就是那个刚好使质点组总动量等于零的惯性系。该惯性系就是相对于质心静止的惯性系，在这个惯性系中质点系的总能量就是质点组的（静）质量（c=1 单位制）。

某惯性系S中质点组的质心总动能 $K_0$ 等于质点组总能量 $E$ 减去质点组的质量 $M^c$ （也就是质点组在质心系中的总能量，这对于任何物体都有效）：
$K_0 = E-M^c$
质点组质量 $M^c$ 等于质心系中所有质点各自的能量 $e^c_i$ 之和，也就等于所有质点的质量 $m_i$ 之和加上所有质点在质心系中的动能 $k^c_i$ 之和：
$M^c = \Sigma e^c_i = \Sigma (m_i + k^c_i)$
质点组总能量 $E$ 等于所有质点的各自的能量 $e_i$ 之和，也就等于所有质点的质量 $m_i$ 之和加上所有质点的动能 $k_i$ 之和：
$E = \Sigma e_i = \Sigma (m_i + k_i)$
质点组总动能 $K$ 等于其中每个质点的动能 $k_i$ 之和：
$K = \Sigma k_i$

所以：

$K_0 = E-M^c = \Sigma (k_i - k^c_i) = K - \Sigma k^c_i$

也就是 $K = K_0 + \Sigma k^c_i$ ，质点组的总动能等于质心动能加上所有质点相对于质心的动能。

如果你对步骤1中把计算动能的公式直接用于质点组不放心，只需证明如果n个质点的质点组满足该关系那么新增一个质点仍然满足这个关系，立即就可以通过数学归纳法证明任意个质点的质点组都满足这个关系（单个质点时该关系被自然满足）。一旦有了这个关系，剩下的就是加加减减。

December 15th, 2010 | 荒唐 | Categories: 心得, 物理 | Comments: No Comments

关于科学松鼠会

某些了解我的人可能会知道，我从一开始就对科学松鼠会的做法不感冒。因为科学松鼠会刚刚建立不久，我就在松鼠会的文章中嗅到了忽悠的气味，经常把价值观私货夹带到科学事实中向公众兜售，让许多人误以为这些价值观私货也是科学事实。松鼠会基本上是把科学当作宗教去传播，但任何宗教都不是科学，因此松鼠会传播的也根本就不是科学。就算松鼠会通过这种方式传播了某些科学事实，但这些零零碎碎的科学事实对于不了解科学的公众而言，跟城隍庙里面那些稀奇古怪的扯淡也不会有太大的区别。这不是问题的关键，问题的关键是科学松鼠会把科学作为宗教来传播，大量兜售价值观私货，这会直接导致缺乏判断力的读者以为这就是科学，把科学方法理解成跟宗教没有本质区别的东西，甚至认为科学就是目前最为成功的宗教。这样的读者，不会通过松鼠会的文章提高自己的判断力，学会冷静思考。如果科普的意义就是把一大堆零零碎碎的在各个学科中的发现的稀奇古怪的事情当作奇谈趣谈灌输给读者，那么这种科普作品对于读者来说起到的作用就跟街边那些关于世界末日大预言，世界几大未解之谜，水知道答案之类的伪科学忽悠没有任何区别。

有人说这至少是一种引起读者对科学产生兴趣的有效方式，让公众更多关注科研领域从而吸引更多科研资金，但我无法同意这种观点。街边那些伪科学著作和松鼠会文章引起读者对“科学”的兴趣的方式是相同的，但这种兴趣根科学方法无关，仅仅是猎奇心态。如果一个人仅仅是出于猎奇的目标进入科学领域，那么他基本上只能成为一个crackpot（科学妄想家）。就算这种方式可能帮助科研领域拉到更多的经费，但既然这些经费来自于公众的猎奇心态，那么当然基本上也就只能投入那些满足公众猎奇心态的项目上，越来越多的科研项目的目标是满足公众猎奇心态，这样的科研环境难道对于科学进步真的是一种帮助么？我严重怀疑。

当然，我为啥要希望科学进步呢？真的不关我屁事。科学的发展很大程度上取决于人们对科学研究的需求和科学研究能够给人们带来的回报。猎奇当然是一种需求，满足猎奇心态当然也算是一种回报，只不过这跟科学已经没有多大关系了。

December 3rd, 2010 | 荒唐 | Categories: 哲学 | Comments: No Comments

关于善恶的对话

A：什么是善行？
B：善行就是令人满意的行为
A：令我满意的行为就是善行？
B：那不一定，你满意别人未必满意
A：那令谁满意的行为才是善行？
B：令多数人满意的行为才是善行
A：如果令我满意的行为恰恰是多数人不满意的怎么办？
B：那么你就应该服从多数人
A：既然多数人反对我，我为什么不能反对多数人？
B：……你斗不过多数人
A：那么令我满意且不会挨斗或反对者斗不过我的行为就是善行？
B：……良心上也得过得去
A：什么是良心？
B：良心就是能够判断善恶的心
A：刚刚说的不就是如何判断善恶么？
B：……

November 30th, 2010 | 荒唐 | Categories: 人生, 哲学 | Comments: No Comments

n-Sphere & n-Ball

Wiki: n-Sphere
$S_{n}$ 是 $V_{n+1}$ 的表面。以下讨论中n-Sphere和n-Ball的半径都是1，半径为 $R$ 的情况乘以 $R^{n}$ 即可。

n-Ball的体积公式：

$\displaystyle V_n = \frac{\pi^\frac{n}{2}}{\Gamma(\frac{n}{2} + 1)} = \frac{\pi^\frac{n}{2}}{\Pi(\frac{n}{2})}$

偶数维体积公式：

$\displaystyle V_{2n} = \frac{\pi^n}{n!}$

奇数维体积公式：

$\displaystyle V_{2n+1} = \frac{2^{n+1} \pi^n}{\left(2n+1\right)!!} = \frac{2^{2n+1} n! \pi^n}{\left(2n+1\right)!}$

n-Sphere的面积公式：

$\displaystyle S_n = \frac{d\left(V_{n+1} R^{n+1}\right)}{dR} = (n+1)V_{n+1} = {2\pi^{(n+1)/2}\over\Gamma(\frac{n+1}{2})} = {2\pi^{(n+1)/2}\over\Pi(\frac{n-1}{2})}$

偶数维面积公式：

$\displaystyle S_{2n} = \frac{2^{n+1} \pi^n}{\left(2n-1\right)!!} = \frac{2^{2n+1} n! \pi^n}{\left(2n\right)!}$

奇数维面积公式：

$\displaystyle S_{2n+1} = \frac{2\pi^{n+1}}{n!}$

递推公式：

$\displaystyle S_{n+1}= \frac{2 \pi}{n} S_{n-1}; \; S_0 = 2, S_1 = 2 \pi$

$\displaystyle V_{n} = \frac{2 \pi}{n} V_{n-2}; \; V_0 = 1, V_1 = 2$

$S_{n+1} = \sqrt{\pi}\frac{\Gamma(\frac{n+1}{2})}{\Gamma(\frac{n}{2} + 1)} S_{n} = \sqrt{\pi}\frac{\Pi(\frac{n-1}{2})}{\Pi(\frac{n}{2})} S_{n};$

$S_{2n+1} = \pi \frac{(2n-1)!!}{2^n n!} S_{2n}, \;\; S_{2n} = \frac{2^n (n-1)!}{(2n-1)!!} S_{2n-1}$

$V_{n} = \sqrt{\pi}\frac{\Gamma(\frac{n+1}{2})}{\Gamma(\frac{n}{2} + 1)} V_{n-1} = \sqrt{\pi}\frac{\Pi(\frac{n-1}{2})}{\Pi(\frac{n}{2})} V_{n-1};$

$V_{2n} = \pi \frac{(2n-1)!!}{2^n n!} V_{2n-1}, \;\; V_{2n-1} = \frac{2^n (n-1)!}{(2n-1)!!} V_{2n-2}$

递推公式的推导（思路是将单位n-Ball分成无数个同轴薄圆柱面，每个圆柱面半径为r，厚度为 $dr$ ，母线是(n-2)-Ball，该(n-2)-Ball的半径为 $\sqrt{1-r^2}$ ）：

$\begin{array}{ll} V_n &\displaystyle = \int_{0}^{1} \int_{0}^{2\pi} V_{n-2}\left(\sqrt{1-r^2}\right)^{n-2} \, r \, d\theta \, dr \\ &\displaystyle = \int_{0}^{1} \int_{0}^{2\pi} V_{n-2} (1-r^2)^{\tfrac{n}{2}-1}\, r \, d\theta \, dr \\ &\displaystyle = 2 \pi V_{n-2} \int_{0}^{1} (1-r^2)^{n/2-1}\, r \, dr \\ &\displaystyle = 2 \pi V_{n-2} \left[ -\frac{1}{n}(1-r^2)^{n/2} \right]^{r=1}_{r=0} \\ &\displaystyle = 2 \pi V_{n-2} \frac{1}{n} = \frac{2 \pi}{n} V_{n-2}. \end{array}$

关系：

$\displaystyle V_n/S_{n-1} = 1/n$

$\displaystyle S_{n+1}/V_n = 2\pi$

一个很有趣的现象是，当n趋于无穷大的时候，单位n-Ball的体积数值随着n增大趋于0：

$\displaystyle \lim_{n\rightarrow\infty} V_n = 0$

这件事有点反直觉，因为感觉上单位n-Ball里面应该总是能够塞进去一个单位n-Cube，但事实上这只是我们在低维空间中总结出来的错误规律。单位n-Ball的直径永远是2，而单位n-Cube的对角线长却是 $\sqrt{n}$ 。n<4时单位n-Cube对角线长小于n-Ball直径，n=4时单位n-Cube对角线长等于n-Ball直径，n>4时单位n-Cube对角线长大于n-Ball直径，而且随着n增大会大得越来越多。也就是说在足够高维的空间中，单位n-Ball里面根本就无法塞入一个单位n-Cube。当然，一个单位nCube里面也不可能完全塞入一个n-Sphere，毕竟单位n-Cube两个相对表面之间的最小距离只有1，而单位n-Sphere直径却是2。

$\Gamma$ 函数的性质：

$\Gamma(z) \equiv \int_{0}^{\infty} t^{z-1} e^{-t} dt, \;\;\;\; \Pi(z) \equiv \int_{0}^{\infty} t^{z} e^{-t} dt$

$\overline{\Gamma(z)} = \Gamma(\overline{z}) \; \Rightarrow \; \Gamma(z)\Gamma(\overline{z}) \in \mathbf{R}$

$\Gamma(z+1) = z \Gamma(z); \;\; \Gamma(n+1) = n \Gamma(n) = n!$

$\Pi(z) = z \Pi(z-1); \;\; \Pi(n) = n \Pi(n-1) = n!$

$\Gamma\left(n+\tfrac{1}{2}\right) = \Gamma\left(\frac{2n+1}{2}\right) = \frac{(2n-1)!!}{2^n} \sqrt{\pi}; \;\; \Gamma\left(\tfrac{1}{2}\right) = \sqrt{\pi}$

$\Pi\left(n-\tfrac{1}{2}\right) = \Pi\left(\frac{2n-1}{2}\right) = \frac{(2n-1)!!}{2^n} \sqrt{\pi}; \;\; \Pi\left(\tfrac{1}{2}\right) = \sqrt{\pi}$

$\Gamma(z) \Gamma\left(z + \tfrac{1}{2}\right) = 2^{1-2z} \; \sqrt{\pi} \; \Gamma(2z)$

$\Pi\left(z-\tfrac{1}{2}\right) \Pi(z) = 2^{-2z} \; \sqrt{\pi} \; \Pi(2z)$

$\Gamma(1-z)\Gamma(z) = \frac{\pi}{\sin{\pi z}}$

$\Pi(-z)\Pi(z-1) = \frac{\pi}{\sin{\pi z}}, \;\;\;\; \Pi(1-z)\Pi(z) = \frac{-\pi}{\sin{\pi z}}$

$\prod_{k=0}^{m-1}\Gamma\left(z + \frac{k}{m}\right) = (2 \pi)^{\frac{m-1}{2}} \; m^{1/2 - mz} \; \Gamma(mz)$

$\prod_{k=0}^{m-1}\Pi\left(z + \frac{k}{m}\right) = (2 \pi)^{\frac{m-1}{2}} \; m^{-(mz+1/2)} \; \Pi(mz)$

November 27th, 2010 | 荒唐 | Categories: 数学 | Comments: No Comments

Notes on Einstein Field Equation

Metric tensor:

$g_{\mu\nu} = g_{\nu\mu}$

$g^{\mu\sigma} g_{\nu\sigma} = \delta^\mu_\nu$

$g^{\mu\nu} g_{\mu\nu} = \delta^\mu_\mu = D$

(D: dimension of the spacetime)

Christoffel symbol:

$\Gamma^\lambda_{\mu\nu} = \frac{1}{2} g^{\lambda\sigma}(\partial_\mu g_{\nu\sigma} + \partial_\nu g_{\sigma\mu} - \partial_\sigma g_{\mu\nu})$

Riemann tensor:

${R^\rho}_{\sigma\mu\nu} = \partial_\mu \Gamma^\rho_{\nu\sigma} - \partial_\nu \Gamma^\rho_{\mu\sigma} + \Gamma^\rho_{\mu\lambda} \Gamma^\lambda_{\nu\sigma} - \Gamma^\rho_{\nu\lambda} \Gamma^\lambda_{\mu\sigma}$

Ricci tensor:

$R_{\mu\nu} = {R^\lambda}_{\mu\lambda\nu}$

Ricci scalar (curvature scalar):

$R = {R^\mu}_\mu = g^{\mu\nu} R_{\mu\nu}$

Trace of energy-momentum tensor:

$T = {T^\mu}_\mu = g^{\mu\nu} T_{\mu\nu}$

Einstein field equation:

$R_{\mu\nu} - \frac{1}{2} R g_{\mu\nu} = 8 \pi T_{\mu\nu}$

$R_{\mu\nu} = 8 \pi \left(T_{\mu\nu} - \frac{1}{2} T g_{\mu\nu} \right)$

Torsion tensor (have nothing to do with energy-momentum tensor $T_{\mu\nu}$ ):

${T^\lambda}_{\mu\nu} = \Gamma^\lambda_{\mu\nu} - \Gamma^\lambda_{\nu\mu} = 2 \Gamma^\lambda_{[\mu\nu]}$

Properties of the Riemann tensor ( $R_{\rho\sigma\mu\nu}=g_{\rho\lambda} {R^{\lambda}}_{\sigma\mu\nu}$ ):

$R_{\rho\sigma\mu\nu} = -R_{\sigma\rho\mu\nu}$

(antisymmetric in first two indices)

$R_{\rho\sigma\mu\nu} = -R_{\rho\sigma\nu\mu}$

(antisymmetric in last two indices)

$R_{\rho\sigma\mu\nu} = R_{\mu\nu\rho\sigma}$

(invariant under interchange of the first and last pair of indices)

$R_{\rho\sigma\mu\nu} + R_{\rho\mu\nu\sigma} + R_{\rho\nu\sigma\mu} = 0$

$R_{\rho[\sigma\mu\nu]} = 0$

$R_{[\rho\sigma\mu\nu]} = 0$

Properties of the Ricci tensor:

$R_{\mu\nu} = R_{\nu\mu}$

Relation between R and T:

$R = -8 \pi T$

Einstein tensor:

$G_{\mu\nu} = R_{\mu\nu} - \frac{1}{2} R g_{\mu\nu}$

so Einstein field equation can be rewritten as:

$G_{\mu\nu} = 8 \pi T_{\mu\nu}$

Geodesic equation:

$\frac{d^2 x^\mu}{{d\lambda}^2} + \Gamma^\mu_{\rho\sigma} \frac{d x^\rho}{d \lambda} \frac{d x^\sigma}{d \lambda} = 0$

Covariant derivative:

$\nabla_\sigma V^\mu = \partial_\sigma V^\mu + {\Gamma_\sigma}^\mu_\lambda V^\lambda$

$\nabla_\sigma W_\nu = \partial_\sigma W_\nu + {\Gamma_\sigma}^\lambda_\nu W_\lambda$

$\nabla_\sigma {T^{\mu_1 \mu_2 \ldots \mu_k}}_{\nu_1 \nu_2 \ldots \nu_k} = \partial_\sigma {T^{\mu_1 \mu_2 \ldots \mu_k}}_{\nu_1 \nu_2 \ldots \nu_k}\\ ~~~~ + {\Gamma_\sigma}^{\mu_1}_{\lambda} {T^{\lambda \mu_2 \ldots \mu_k}}_{\nu_1 \nu_2 \ldots \nu_k} + {\Gamma_\sigma}^{\mu_2}_{\lambda} {T^{\mu_1 \lambda \ldots \mu_k}}_{\nu_1 \nu_2 \ldots \nu_k} + \ldots\\ ~~~~ - {\Gamma_\sigma}^{\lambda}_{\nu_1} {T^{\mu_1 \mu_2 \ldots \mu_k}}_{\lambda \nu_2 \ldots \nu_k} - {\Gamma_\sigma}^{\lambda}_{\nu_2} {T^{\mu_1 \mu_2 \ldots \mu_k}}_{\nu_1 \lambda \ldots \nu_k} - \ldots$

Energy-momentum tensor:

$\nabla_\mu T^{\mu\nu}=0$

November 24th, 2010 | 荒唐 | Categories: 数学, 物理 | Comments: No Comments

价值观之争

任何价值观都只不过是复杂程度不同的偏好，关于偏好的争论在逻辑上就不可能有结果。

任何单纯的价值观争论都必然无果，原因就在于任何主张『所有人都应该认可×××』的价值观都杯具地对所有人做出『要求』，只要是『要求』，就绝不是『经验假设』。只有『经验假设』才可能被验证，而对于任何形式的『要求』，只能谈论它能否被一个特定的人所接受，根本不能谈论对一种『要求』的验证。凡是不能被验证的东西，自然就不能谈论什么对错（更准确的词汇是『有效性』）。

另一方面，价值观可以被分析，分析的方法就是追溯其更基本的需求，也就是不断询问『你采取某种价值观是为了得到什么』、『你反对某种价值观是为了得到什么』。通过这种追溯过程可以发现个体之间需求的相似性。但千万注意不要进入下一个误区：两个个体需求相似，根本不意味着双方的利益是一致的。比方说我和你都需要同一块土地，那么我们之间需求的相似性恰恰是利益冲突，这种情况下接下来的问题是双方的博弈。

1.你所主张的未必你的基本偏好，只是你达成更基本的偏好目标所采取的手段。
2.只要你的某个主张是为了达成某些目标，那么这个主张就不是基本偏好，因为那些目标显然更基本。
3.是否存在不同的手段能够更好的达成某个目标，显然是经验科学问题；你认为好的事情，别人是否也认为好，显然也是经验科学问题。
4.对于经验科学问题，如果经验科学方法尚不能给出有效判断，那么任何非经验科学的方法（包括信仰和想当然）也不能。如果试图给出有效判断，价值观争辩毫无帮助。

人都有偏好，要么认为这东西好，要么认为那东西好。但所有的『××主义者』都不同，他们不但认为某些西好，还进一步认为『所有人都应该认可这些好东西』。无论从什么样的逻辑推理规则或者经验科学事实出发，任何形如『所有人都应该×××』的语句都只能从形如『所有人都应该×××』的语句推出，这种句子甚至不能从形如『我个人应该×××』或『我个人认为所有人都应该×××』的句子推出，也就是说所有能给出『所有人都应该×××』这种判断的理论，其最基本前提必须包括形如『所有人都应该×××』的句子。而无论采用什么样的经验科学事实或个人价值观作为前提，一个理论都不可能导出形如『所有人都应该×××』的结论。换言之，凡是这样的价值观理论，从一开头就必须是法西斯式的。遗憾的是，这种从一开头就法西斯式的理论，折腾出来的结论看上去往往都很吸引人，甚至好像是反法西斯的，比方说共产主义、民族主义、社会达尔文主义、动物保护主义、绿色和平主义、普世价值、客观道德、天赋人权、人人生而平等、众生平等（上述词汇之间既不是并列关系也不是因果关系也不是主从关系也不是顺序关系……随便你认为它们之间是什么关系）……

即便是形如『我认为人人都应该×××』这样的前提，无论结合什么样的逻辑推理或经验科学事实，所能导出的也只能是『我认为人人都应该×××』，不可能导出『人人都应该×××』。

不知道大家是否看过赵南元关于宣传型理论和自用型理论的文章。我做个自爆：在我的自用理论之中，我绝不是任何上述意义上的『××主义者』，而且任何真心把上述意义上的某种『××主义』当作自用型理论的人在我看来全是傻逼。当然，通常很难从一个人的公开表现判断出他到底是装傻逼还是真傻逼。我当然有我自己的偏好，但至少我的自用型理论绝不主张『人人都应该×××』或者『人人都应该反对『人人都应该×××』的主张』，因为这些主张对于任何人的行为决策在逻辑上就不可能提供任何帮助，只能提供心理安慰，同时降低他对经验事实的判断能力，而这恰恰是我根本不想要的。另一方面，我也有可能在某种情况下为了自己的私利而对别人假装成某种『××主义者』，也就是说我的『宣传型理论』也未必直接反映我的动机。因为宣传型理论本来就是利用自用型理论所构造出来的达成自己目标的工具和手段。

由于我自爆了关于我自己的实话，今后想要因为一己私利而装傻逼就会面临更高的壁垒，不过我个人倒是真心希望在这个社会中我不需要总是装傻逼才能得到我想要的东西，因为这既不是我擅长的也不是我爱好的。

November 22nd, 2010 | 荒唐 | Categories: 哲学 | Comments: No Comments

评：物理学的逻辑和霍金的答案

物理学的逻辑和霍金的答案
http://www.geekonomics10000.com/546
——————————————
评：

把科学当信仰去信奉的人试图反驳一个以信仰为生的牧师当然是徒劳的，当然这种人所信奉的东西也并不是科学，而这种信奉的做法也不是科学的精神。

关于上帝有无穷多互不相容的逻辑自洽的理论。比方说上帝创造各种年龄的化石和自然现象给人看，那他可以在100亿年前创造，也可以在昨天创造，甚至可以在明天创造世界，然后把时间倒着拨……只要这些理论无法在经验活动中得以区分，那么就都可以是真的，也都可以是假的，偏爱其中任何一种都是盲目的，而任何一种宗教恰恰仅仅是其中一种。而经验科学必须给出可以通过经验区分的结论，凡是跟经验毫无逻辑关系的概念在经验科学中都是多余的。

搞科学的人经常拿奥卡姆剃刀剔除这些概念，但对于一个信徒来说他可能恰恰认为某些关键的概念恰恰是无法被经验验证的，所以他会认为奥卡姆剃刀恰恰把最关键的东西给剔除了，因此他们会拒绝使用奥卡姆剃刀。但事实上根本没有必要把奥卡姆剃刀上升到基本的地位，奥卡姆剃刀剔除不掉的东西，总会有无穷多种互不相容的选择，随便你选择其中的哪一种去坚信，你的所坚信选择都仅仅是随意的盲信。

PS：

有人说：物理学的假设只很少几个，而关于万能上帝的假设太多了。假设少的更可信。

是否假设越少越可信，上述观点教徒未必认同。关键是无法检验的假设有无限的可能，无法检验自然无法有证据，既然这些假设都没有证据，那么认为其中某一个特定的可能比其他的可能更可信就是随意的。教徒愿意随意盲信当然没问题，但他如果敢为了传教而宣称这些东西是可靠有根据的，就是撒谎，而判断他是否在随意的信仰上撒谎，标准是明确可操作的。

November 2nd, 2010 | 荒唐 | Categories: 哲学 | Comments: No Comments

在Wikiquote上搜到了我签名格言在其他几种语言的等价版本

Wikiquote

只认识英文，把这些等价的版本都翻译成英文写在下面：

The road to hell is paved with good intentions.
English, Polish, Romanian

Hell is paved with good intentions.
French

Hell is full of good intentions.
Portuguese

Good intentions could turn out to be evil in the end, or good intentions could be impossible to implement and could only lead to suffering.
Dutch

我的汉译版本：
地狱之路，善意铺就。

October 16th, 2010 | 荒唐 | Categories: 人生 | Comments: No Comments

囚徒的生机

问题

100个无期徒刑囚徒被关押在100个单独的房间内，彼此无法互相通信。典狱长会不定期地随意让一个囚徒出来放风（有可能重复）。放风处只有一盏灯，灯是亮是灭，只有放风的人能看到，被放风的囚犯可以改变灯的开关状态。

有一天典狱长把100个囚徒召集起来对他们宣布，从现在开始，今后如果你们当中有任何人能够确证所有的人都至少被放风过一次，那么你们全都可以被释放，如果判断错误就会被全体处决。给你们一段时间让你们一起研究一下怎么做。然后各自回各自的房间。

分析

$N$ 个囚犯，第 $i$ 次被放风的囚犯编号为 $p_i, p_i\in [0,N)$ 。约定每次被放风的囚犯是否改变灯的开关状态的决定为 $x_i, x_i\in \{true, false\}$ ，每次放风前灯的状态为 $s_i,s_i\in \{on, off\}$ 。显然有： $x_i=(s_{i+1}\neq s_i)$ 。而每一个人在第i次放风时做出决定时所拥有的信息只有自己曾经被放风的那些次灯的原来状态 $x_i = f(S_i), S_i = \{s_k\vert p_k = p_i, k\le i\}$ 。

在第 $k$ 次放风时，被放风的囚徒 $p_k$ 必须根据 $S_k$ 来判断是否所有的囚徒都曾经被放过风了。

变种

规定是每天有一次放风，于是每个囚犯被放风的时候还知道当天是第几天。如果他连续两天被放风，他可以确定中间没有其他人曾经被放风。
规定必须至少有两个囚犯都可以确定所有人都曾经被至少放风过一次所有人才能得到释放。
规定有两盏灯，但所有的囚犯必须采取相同的策略。

Matrix67的讨论：
http://www.matrix67.com/blog/archives/3618
http://www.matrix67.com/blog/archives/3630
全文转贴：

100个囚犯和灯泡的那些事儿

说有 100 个囚犯分别关在 100 间牢房里。牢房外有一个空荡荡的房间，房间里有一个由开关控制的灯泡。初始时，灯是关着的。看守每次随便选择一名囚犯进入房间，但保证每个囚犯都会被选中无穷多次。如果在某一时刻，有囚犯成功断定出所有人都进过这个房间了，所有囚犯都能释放。游戏开始前，所有囚犯可以聚在一起商量对策，但在此之后它们唯一可用来交流的工具就只有那个灯泡。他们应该设计一个怎样的协议呢？

这个经典的问题在网上转载无数，题目描述被好事者们改得天花乱坠，甚至加进了“这盏灯永远有充足的能源供应”、“如果灯泡坏了或是电路出了故障会马上修好”等条件，剥掉了“算法问题”的外壳，填补了本不存在的漏洞，让更多的人动起了脑筋。在论坛上，每次贴出这个问题，总会引起一大群人的口水战。但很不幸的是，这个题目的来源至今仍是个谜。据目前的已知情况推测，这个题目最早来源于 Berkeley 的电气工程荣誉学会，时间大概是 2001 年。在 2002 年的 7 月， IBM 的 Ponder This 趣题栏目介绍这个题目，囚犯与灯泡一炮走红，随即遍布网络的各个角落。 2003 年， The Mathematical Intelligencer 杂志上发表了一篇题为 One hundred prisoners and a lightbulb 的论文，也让囚犯们正式引起了数学家们的关注。

相信这个问题的答案大家已经非常熟悉了，不过这里我想用另一种更玄乎的、更具启发性的方式重新讲述一下答案。

不妨幻想房间中有一个盒子，盒子里可以容纳一个小球。灯泡亮就表示这个假想的盒子里有一个假想的小球，灯泡不亮就表示这个假想的盒子是空的。因此，用开关控制灯泡就相当于在盒子里放进小球或者取走小球。初始时，每个囚犯手中都有一个小球（当然这个小球也是囚犯们自己意淫出来的）。游戏开始前，囚犯们选择一个代表作为统计者。之后，每次有囚犯进入房间后，如果小球还在他手里，盒子恰恰又是空着的，他就把小球放进去；而统计者的任务就是收集小球——每次进入房间后，看到盒子里有小球就把它拿走。如果某个时刻统计者手中集齐了（包括它自己的） 100 个小球，就说明所有人都进过房间了。

这个简单而巧妙的协议让人大为折服。然而，对这个问题的讨论并未结束，计算协议完成所需的期望时间、设计期望时间更短的协议，这都是非常有挑战性的问题，虽然它们已经背离了这个问题的初衷——协议的设计。这篇论文里详细总结了著名数学趣题论坛 [wu::forums] 上的牛人们对上述问题的探索。不过，即使回到协议设计的话题上，这个题目也还有戏可唱。
现在，让我们来考虑这个问题的一个加强版。上述策略能成功的原因是，大家都知道房间里的灯泡一开始是不亮的（盒子里一开始没有小球）。如果灯泡的初始状态并不确定，那就麻烦了：统计者收集了 100 个小球并不足以说明所有人都来过房间，而他有可能永远也等不到第 101 个小球。那么，这个问题还有解吗？在继续想下去之前，你不妨先思考一下。

是的，这个问题仍然有解，而且办法和原来几乎一样，只是有一些非常巧妙的变通。此时，“小球模型”开始发挥作用了：在引入了一些更加复杂的因素后，比起开灯关灯，用“小球语言”来描述显得更直观易懂。

囚犯们仍然选出一个统计者，由他来完成收集小球的任务。只不过这一次，每个囚犯初始时都有两个（假想的）小球。每个囚犯来到房间后，如果发现盒子是空的，手中正好还有小球的话，他就在盒子里放一个小球。统计者仍然只负责把小球从盒子里取出来。什么时候统计者收集到了200个小球（包括自己的两个），他就知道所有人都来过了，因为如果还有人没进房间，他最多只能拿到 198 + 1 个小球。注意，这 200 个小球可能就是囚犯手中的 200 个小球，也有可能是囚犯手中的 199 个小球加上初始时房间里的小球。体会一下这个协议如何巧妙地解决了房间初始状态不确定的难题，真是越想越有味道。

还不过瘾吗？现在与大家分享一个更强的加强版。

在以上协议中，只有一个人能知道所有人都来过房间。是否存在一个协议，使得最终可以产生两个人，他们都知道所有人都进过房间？如果存在这样的协议，给出一个来；如果不存在，证明之。为了方便思考，你可以暂时假设初始时房间的灯泡不亮。

不要轻易就认定这是不可能的。至少当 n = 2时，这样的协议明显存在！

即使灯泡的初始状态不定，当 n=2 时，两个人也能保证都知道对方进过房间。假设双方手中各有两个球，囚犯 A 总是试图把自己的小球放进盒子，囚犯 B 总是试图把小球取走。如果 B 拿到了 4 个小球，他就知道了 A 一定来过房间；而只要 A 放好的小球被拿走了， A 也知道 B 进过了房间。

但是，当 n>2 时，不存在这样的协议，使得有两个人都能获知所有人都已进过房间。 Peter Winkler 的 Mathematical Puzzles: A Connoisseur’s Collection 一书中给出了这个结论的一个大致证明思路。

让我们考虑其中任何一个囚犯。我们假设他的策略是确定性的，他的下一步行动完全取决于之前看到的状态序列。假设在某一步，他看到的状态和上次离开房间时的状态相同，但他选择了改变状态。这时，你可以质问他，那你为啥不在上次就把状态改过来，偏偏要这次才去扳开关呢？看守完全有可能连续两次都是叫你进的房间，这样你不就浪费了一次进房间的机会了吗？因此，我们可以假设，当他进入房间时看见的状态和上次走的时候一样，他是不会去扳动开关的。

接下来，让我们假设在某一步，这个囚犯的策略是“不动开关，保留原状态”。那么，我们可以认为他以后就再也不会动那个开关了！因为在最坏情况下，他根本没有改变灯泡状态的机会！具体地说，若无视掉这个囚犯以后的行动，今后的房间状态序列里必然有一种状态将出现无穷多次，比方说状态“开”出现了无穷多次吧。那么在最坏的情况下，这个囚犯从此开始总是在开灯的时候进屋。而他在这一步没有变动开关，并且以后的每一步里他所看到的状态都将和上次看到的一样，因此以后他都不会变动开关了。

因此，这名囚犯首次进入房间时的策略绝不可能是“不动开关”，因为这样他以后可能都没机会动开关了，没人会知道他来过房间。如果他的策略是“如果灯开着，就把它关掉”，那么由第一个引理，今后他看见关灯状态都不会去改变状态了，直到下次见到灯亮时才会有所行动。每次见到灯亮时，他有两种选择，把灯关掉，或者让它接着亮。如果选择关灯，他又要等到下次灯亮才会行动；如果不关灯的话，相当于他这次没做任何操作，今后就再也没法行动了。也就是说，他的整个策略无非是“关过多少多少次灯之后就不管了”。类似地，如果他首次进入房间时的策略是“如果灯关着，就把它打开”，同理可知他今后的策略限制在了“再开几次灯就不开了”。当然，首次进入房间的策略还可能是“无论状态如何，总是扳动开关”，不过实际情况一揭晓，他的策略也就立即归为了上述两种情况中的一种。

换句话说，每个人的策略都无外乎两种：只负责开 x 次灯，或者只负责关 x 次灯。当然，如果所有人都只开灯不关灯（或者只关灯不开灯），肯定是一点用处都没有。因此，无妨假设囚犯 A 负责开灯，囚犯 B 负责关灯。如果囚犯 C 也只负责开灯， A 永远不能分辨出 B 、 C 究竟是都完成了协议，还是都差最后一步；如果囚犯 C 只负责关灯， B 就成了那个被蒙在鼓里的人了。
也就是说，整个问题的唯一解法就是，其中一个人只负责关灯，另外所有人只负责开灯；或者其中一个人只负责开灯，另外所有人都只关灯。换句话说，我们的“统计者协议”其实是唯一的解法。

在 Mathematical Puzzles: A Connoisseur’s Collection 一书中，我们有幸看到了这个问题的另一个更加有趣的变种，让囚犯们的难题继续活跃着人们的大脑。
还是 100 个囚犯，还是一个空房间，还是要求所有囚犯事先构造一个协议，能保证有人可以断定出所有人都来过房间。不过，这次不同的是，房间里有两个灯泡，分别由两个开关来控制（不妨假设初始时他们都是不亮的）。大家估计要说了，一个灯泡都能解决的事儿，用两个灯泡还不容易？嘿嘿，这次有一个附加的要求：所有人都必须遵循同一套策略。

这些智力游戏不仅仅是思维的体操，它竟然有不少让人意想不到的实际应用。远在这个智力题诞生之前，就有一个几乎等价的分布式计算难题困扰着人们：假如一个程序有 n 个进程，它们操作的是同一段（不太宽裕的）公共内存。但在程序运行中，有些进程可能会崩溃掉。我们希望程序能报告出当前还有多少个进程在工作，但使用的空间越少越好。一个简单的解决方案就是，预先指定一个进程作为统计者，照搬囚犯们的策略，只消一个 bit 即可统计出活动进程的大致数量。但问题是——这个统计进程崩溃了咋办？因此，为了避免有关键进程崩溃，这些进程的行为必须得一致才行。 1990 年， Michael J. Fischer 、 Shlomo Moran 、 Steven Rudich 、 Gadi Taubenfeld 四位牛人共同发表了一篇叫做 The Wakeup Problem 的论文，提出了著名的跷跷板协议 (see-saw protocol) ，成功解决了这一难题。

我们还是把其中一个开关想象成一个盒子，它里面只能放一个小球。再把另一个开关想像成一个跷跷板，它也只有两种状态：左低右高、左高右低。要想改变跷跷板的倾斜方向，只能扳动它的开关。初始时，每个囚犯手中都有一个（假想的）小球。每个囚犯第一次进入房间后，他都幻想自己坐到跷跷板低的那一边上，然后把自己这一侧扳高。以后每次回到这个房间时，他都看看自己所在的那一侧是高还是低：如果是低的话，他就取走盒子里的小球（如果有的话），于是手中就多了一个小球；如果是高的话，他就在盒子里放一个小球（如果盒子是空的），此时手中的小球就少了一个。注意，如果他把手中的最后一个小球放进盒子了（此时他手中没有小球了），他就必须从跷跷板上下来，把自己所在的那一侧扳低，之后就再也不进行任何操作了。如果有某个囚犯收集到了 100 个小球，显然他就知道所有人都来过房间了。问题的关键就是：为什么最终总会有一个人能集齐所有的小球？

其实，协议中的很多复杂的细节都是为了保证下面这个引理成立：每一个人离开房间之后，房间里都只可能有两种情况：

A. 跷跷板两侧的人一样多
B. 高的那边多一个人

这是因为，如果有囚犯第一次进入房间，他将坐上低的那一侧，并把那一侧扳高，于是原本是情况 A 现在就会变成情况 B ，而情况 B 则会变成情况 A ；另外，如果有囚犯下了跷跷板，高的那一侧将少一人，同时该侧将被扳低，同样有情况 A 将变情况 B ，情况 B 将变情况 A 。

现在，让我们假设所有人都进过房间了，并且有 k 个人正在跷跷板上（其余的人都已经离开跷跷板了）。由于跷跷板两侧最多差一人，因此当 k 大于 1 时，跷跷板两侧都是有人的。而由于每个人都进过房间了，因此不会有新的人坐上跷跷板了。此时，位于高处的人将不断拿出自己的球，并被位于低处的人取走。直到某个时刻高处有人拿不出小球了，他将走下跷跷板，此时跷跷板的状态才会发生变化，跷跷板上的总人数将变成 k-1 。最后跷跷板上只剩一个人时，显然他就拥有了所有人的小球，此时他就知道所有人都来过了。

容易想到，如果初始时房间的状态不定，人手两个球的改进方法同样能解决问题。当然，对问题的探索是永无止境的，我们相信囚犯与灯泡的问题还会有更多漂亮的变种和扩展，不断启发着人们的思维。即使这些问题没有任何使用价值，思考过程本身也是有益而有趣的。让我们感谢最初设计这个智力趣题的无名氏，他给我们带来了无尽的思维乐趣。

October 10th, 2010 | 荒唐 | Categories: 哲学 | Comments: No Comments

从计算观点开始……（草稿）

孤立物理体系

所谓孤立物理体系，是指这个体系完全不受其他体系影响，体系的可能状态由体系自身的物理规律所决定。假定为体系选择的一组状态参数的所有取值构成的集和为 $S$ ，那么物理规律就限定了这个集和中那些状态是物理规律所允许的，相当于是对集和 $S$ 的一个约束。可以记为：
$K[s], s\in S$
其中， $K$ 是一个判断， $K[s]$ 为真当且仅当状态 $s\in S$ 是物理规律所允许的。
将所有这样的状态构成的集合记为 $K[S]$ ，显然有 $K[S]\subseteq S$ 。
如果我们的状态参数选取得非常好，参数空间中每一个参数都对应一个符合物理规律的状态，我们就全知了。可惜我们做不到，我们所选择的状态参数所构成的参数空间总是远大于物理规律所允许的状态集。退而求其次，我们希望找到一种等价关系，这种等价关系将状态空间划分为若干个等价类，所有物理规律允许可以共存的现象事件都仅仅属于其中一个等价类，而这个等价类也仅仅包含物理规律允许的现象事件。这样，我们只要找到了这个等价类中的一个代表状态，就可以确定整个等价类。这就是通过初值条件或者边界条件来求解物理体系的方法。

一个简单的例子：一个沿直线匀速运动的粒子，其状态由 $(x,t)$ 标记，运动方程为 $x=v t+x_0$ ，那么仅当 $(x,t)$ 满足这个运动方程时，我们才认为由 $(x,t)$ 所标记的状态才是物理规律所允许的状态。这个例子中所有物理规律所允许的状态的集和刚好构成了粒子的世界线。再举个一维经典标量场的例子：场 $A$ 的状态由函数 $A(x,t)$ 决定。仅当 $(A,x,t)$ 满足场方程 $\frac{\partial^2 A}{{\partial t}^2}-\frac{\partial^2 A}{{\partial x}^2}=0$ 和某个边界条件（例如初始条件 $A(x,0)=A_0(x)$ ）时，我们才认为 $A(x,t)$ 是物理规律所允许的状态。

但上述模型对于物理学家来说只是运动学（Kinematic）模型，只有当你了解了宇宙状态的所有细节才能给出这个运动学方程，而这些细节恰恰是我们希望能够通过方程预言的。换言之这种抽象的运动学模型没什么用。物理学家希望的是：当我了解了宇宙局部的某些信息之后，我可以通过这些信息推算出另一些局部甚至全局的信息。这就要求我们建立所谓的动力学（Dynamical）模型。如果我们知道了宇宙的全部运动学信息，那么动力学模型总是可以导出的，但我们了解到的只是一些局部的信息。

以一维匀速直线运动为例，当我们知道了某个 $(x_0,t_0)$ 是合法物理状态，那么从动力学方程 $\frac{dx}{dt}=v$ 就可以推算出其他的合法物理状态，这个方程告诉我们，如果 $(x_0,t_0)$ 是合法物理状态，那么 $(x+dx,t+dt)$ 要满足什么条件才是合法的物理状态。也就是说，该动力学方程给出了 $(x_0,t_0)$ 和 $(x+dx,t+dt)$ 必须满足的关系，积分后就可以得出 $(x_0,t_0)$ 和任意 $(x_1,t_1)$ 的关系。物理学的动力学视角写成数学方程就是：
$D[S_0,S]=K[S],~where~S_0\subset K[S]$
限定了 $S_0$ 和K[S]必须满足的关系。显然，最平凡的情况是 $S_0=K[S]$ ，但物理学家希望从一组尽可能小的 $S_0$ 出发，通过 $D$ 能够得出整个 $K[S]$ 。比方说匀速直线运动的例子中，从任何一个单独的 $(x_0,t_0)$ 就可以得到所有合法的物理状态。而在上述的一维经典场论中，单独的一个 $(A,x,t)$ 是得不出所有合法物理状态的，必须了解一组状态，比方说了解 $t$ 为某个定值的时候所有 $x$ 对应的 $A$ （初值问题），或者了解曲线 $f(x,t)=0$ 上所有的 $A$ （边值问题），或者了解曲线 $f(x,t)=0$ 上所有的 $\partial A/\partial t, \partial A/\partial x$ （边值问题）。

在经典绝对时空观之中，时间是一个非常特殊的状态参数，所有其他的状态参数都可以写成时间的函数，对于实数、复数、向量、张量等形式的物理量，都可以表达为时间的函数，对于许多物理问题而言，我们都可以根据初值来决定今后的演化：
$D[K[S]|_{t=t_0}, S]=K[S]$
这样一来，这就是所谓经典的机械决定论的视角。进一步，我们可以把这种方程写成关于时间的演化方程：
$K[S]|_{t^+}=F[K[S]|_t]$
如果模型中的时间是连续的，那么可以直接表达为微分方程，令 $s(t)=K[S]|_t$ ：
$\partial s/\partial t=f(s,t)$
在相对论之中，时间不再具有特殊地位，不同参考系也没有一个标准时间，但大家仍然希望能够在时间上做出预言，一个办法是给出物理量在某个完整的类空超曲面上的值，以至于所有的类时世界线都会与这个类空超曲面相交，就可以决定整个时空流形的物理量了。

另一方面，最初用来标记系统状态的状态参量可能具有若干对称性……（待续）

虽然真正的孤立体系要求完全不受外界影响，以至于这样的体系不能从外部通过相互作用来观测，但最初人们认为我们总是可以设法在技术上降低观测对体系的影响，使被观测的体系几乎跟孤立体系没有区别。但近代物理学让人们改变了这种想法，当我们对被观测体系的了解越来越精细，就不得不越来越多地与之相互作用。这种情况下我们需要的是一个相互作用的理论模型，而不是一个孤立体系的理论模型。……（待续）

量子力学实验中往往把宇宙划分为3个部分：被测系统S，观察者和仪器O，环境E。通常要求S只跟O相互作用，但不允许受到E干扰。量子力学的原理体系中扣掉测量原理，描述的就是一个孤立体系的演化。本来应该能够通过孤立体系的演化方程得出一个相互作用的方程，然后计算出观察者观察被测体系将会得到什么结果，但最初大家不知道怎样算，没人会求解整个宇宙的Schr?dinger方程。于是物理学家从实验中得到了一条经验规律：测量原理。遗憾的是测量原理被上升到了量子力学基本原理的地位，引发了Einstein和Bohr旷日持久的争论。到了近代人们逐渐发现测量原理在许多条件下是可以导出的，而且导出的结果比测量原理所给出的细节更多。

————（可逆性、对称性、熵增、可观察量、规范……）

————（引入动机的数学模型，然后是偏好的评价函数，心理，行为，经济，博弈，生态系统，社会……）

开放的物理体系，相互作用

一个孤立体系可以被人为地通过边界划分为两个子系统，这两个子系统通过边界发生相互作用。每一个子系统的所有合法状态自然仍然由整个系统的运动学方程所谓一决定，但我们需要的是得到其中一个子系统的方程，这个方程只跟这个子系统的状态以及另一个子系统在边界上的状态有关……（待续）

孤立机器

所谓孤立机器，就是指这样一种东西：其任意时刻的状态演化方式完全取决于该时刻的状态。
将孤立机器的状态记为 $S$ ，时间记为 $t$ ，后继（Successor）时间记为 $t^+$ （比方说在t连续的情况下， $t^+:=t+dt$ ，离散情况下 $t^+:=t+1$ ），演化规律记为 $U$ ，那么上述定义相应的数学模型为：
$S(t^+) =U[S(t)]$
经典力学中的Hamilton方程就是描述这种孤立机器的方程。在Hamilton力学中，体系的状态用所有粒子的位置和动量来标记，而Hamilton方程则决定了体系状态的演化机制。
$(p,q)(t+dt) = (p,q)(t) + \left(-\frac{\partial H}{\partial q}, +\frac{\partial H}{\partial p}\right)dt$
还有量子力学方程 $\left| \psi (t) \right\rangle = e^{-\mathrm{i}H t}\left| \psi (0) \right\rangle$ ，此时 $U = e^{-\mathrm{i}H t}$

机器

所谓机器，就是指这样一种东西：

跟环境之间有一个分界线
环境在边界上的状态作为机器输入可以改变机器状态
机器在边界上的状态作为机器输出可以改变环境状态
任何时刻其行为和内部状态的变迁完全由该时刻的内部状态和环境输入唯一决定

如果环境也是一台机器，那么可以将环境的状态记为E，那么相应的数学模型为：
$S(t^+) = U[S(t), \partial E(t)]$
$E(t^+) = U[E(t), \partial S(t)]$

孤立机器是机器的特例，如果将环境和机器当作一个孤立整体，那么它又会变为一台孤立机器：
$(S,E)(t^+) = (S(t^+),E(t^+)) = (U[S(t),\partial E(t)],U[E(t),\partial S(t)]) = U[(S,E)(t)]$
如果把系统作为一个整体考虑，那么无论在机器和环境之间如何划界，对结果都是无影响的。

离散的孤立机器

所谓离散的机器，就是上述孤立机器定义中，状态变迁是按步骤跳变的，具有可数内部状态。
对于这样的机器，我们可以用步骤编号 $i$ 代替时间 $t$ ，用 $i+1$ 代替 $t^+$ 。于是其数学模型为：
$S_{i+1} =U[S_i]$

离散的机器

所谓离散的机器，就是上述机器定义中，状态变迁是按步骤跳变的，具有可数内部状态，对环境输入的分类能力也是可数的。
这样一台机器，其时间由步骤标记，记为 $i$ ，于是：
环境从边界给机器的输入记为 $\partial E_i$ ，机器从边界对环境的输出记为 $\partial S_i$ ：
$S_{i+1} = U[S_i, \partial E_i]$
$E_{i+1} = U[E_i, \partial S_i]$

有限状态机器

如果离散的机器的状态数量是有限的，而且只能对环境输入做有限种分类，就叫做有限状态机器。但环境的状态可以是无限的，我们利用有限的时间和资源能够制造出这种机器。图灵机就是一种这样的机器。

图灵机

图灵机是一台有限状态的机器，对于图灵机来说，其环境就是一条无限长的格子纸带（因此环境拥有无限种状态），这个纸带的每一个格子都存贮一个符号，符号的种类是有限的。每一个步骤中，图灵机停泊在纸带上一个特定的位置，可以从这个位置读取符号，然后根据自身状态和读取到的符号唯一地作出一个动作，动作包括向当前位置写入一个符号，然后向左或向右移动一个格子，将自身状态迁移到新的状态。

除此之外，图灵机有一个特殊状态：起始状态，作为每一次执行计算任务的过程的初始状态。还有一组状态作为结束状态，其中一部分被标志为接受，另一部分被标记为拒绝，表示计算任务执行的后果。

可以证明，凡是能够用有限状态机器完成的计算任务，用图灵机都可以完成。还有人进一步证明，通常的神经网络计算模型的计算能力完全等价于图灵机，所谓通常的神经网络计算模型是指这样的神经网络：每一个神经元仅仅有有限种（典型是两种）兴奋状态。

但物理系统经常不是有限状态机器，因此不能简单地说所有的物理系统都等价于图灵机。但是，如果一个由连续参数描述的物理系统，如果对于人类来说可以通过物理量来区分的状态是有限的（比如由于热噪声的存在导致的测量误差），那么这个物理系统对于人类来说计算能力就并不比一个有限状态机器更强。

September 27th, 2010 | 荒唐 | Categories: !Engic, 哲学, 数学, 物理, 算法 | Comments: No Comments

Feynman路径积分实际上就是传统光学的Huygens-Fresnel原理

Feynman路径积分和Huygens-Fresnel原理都可以用Green’s Function和Fourier transform进行计算。

September 27th, 2010 | 荒唐 | Categories: 心得, 物理 | Comments: No Comments

不道德的蚊子#非正常人类对话系列#

『这里所说的#非正常人类#是哪种人？就是特指那些因为闲的蛋疼以至于会为了一点点鸡毛蒜皮的小事就煞有介事地深入分析动辄上升到三观高度的童鞋们。另一方面他们的行为也并非不可理解，他们爱好思考就像许多人爱好音乐、运动、美食、旅游一样，只是人群中像他们那样喜欢深入思考刨根问底的个体很少，所以才显得很不正常。』

甲：MD，昨晚又被叮了一身包，这些可恶的蚊子太缺德了。

乙：是啊，蚊子让人无法理解，非要偷别人的血喝，完全没有自己劳动创造食物的觉悟。

甲：他们怎么会有觉悟，他们天生是蚊子，靠本能支配，不吸血会饿死。

乙：哦，原来如此！如果我是只蚊子，宁可饿死也决不干偷偷吸血这种缺德事儿。

甲：所以像你这样的蚊子都死光了，活下来的蚊子都偷偷吸血。

乙：对，这些蚊子显然道德败坏，根本不懂舍生取义的道理。

甲：你真会说笑，它们只是受本能支配，又没有选择的自由，谈不上道德不道德。

乙：你不是说它们偷别人的血很缺德么？

甲：那只是因为我昨天被叮惨了，发泄下情绪而已。

乙：它们出于生存本能咬了你，你就骂它们缺德，有点不厚道吧。

甲：呵呵，是啊，毕竟蚊子不是人。

乙：人偷东西为什么就缺德呢？

甲：因为这伤害别人。

乙：蚊子也伤害了你。

甲：这不一样，蚊子出于生存本能，没得选。

乙：人偷窃别人的东西都是有的选的？

甲：那当然，人有选择的自由。

乙：大家都有选择的自由，为什么有些人会选择偷？

甲：他们人品不好。

乙：为什么有些人人品不好，另一些人人品好呢？

甲：可能的原因很多，说不定跟小时候生存的环境和教育有关，说不定跟基因中的某些东西也有关。

乙：这些东西能选么？

甲：……不能选。

乙：既然不能选，也就是说一个人品不好的人之所以成为人品不好的人，并不是他能够选择的。

甲：……未必吧，好像有些人会选择努力避免自己成为人品不好的人，而另一些人不会。

乙：为什么有些人会选择努力避免自己成为人品不好的人，而另一些人不会？

甲：因为……他们人品不好……哦，我又绕回去了。……应该还是跟他们的经历有关，比如环境、教育、基因等等。

乙：既然如此，仍然不是他们自己可以选择的。

甲：……好吧，我知道你的意思，你的意思是说一个人选择做坏事，跟他的人品有关，而恶劣人品的形成并非是他能够选择的。

乙：难道不是么？

甲：但是按照你这种说法，那么世界上的坏人就都没有罪过了，一个人做坏事也不应该受到惩罚了，法律和道德也就不存在了。

乙：为什么？

甲：因为人没有自由。

乙：为什么没有自由？另外为什么没有自由就不需要对自己做过的坏事负责？

甲：没得选，自然就没有自由。没有自由，那么坏人就是命运安排的，既然是命运安排的，那么坏人也就没有什么责任了。

乙：蚊子也没得选，你为什么还要打死它？

甲：……我难道任由它吸我的血？

乙：坏人没得选，难道别人就得任由他们作恶？

甲：不对，这个逻辑得原回来，蚊子咬我没得选，但我打蚊子也没得选。

乙：这不就结了，坏人作恶没得选，其他人惩罚坏人作恶也没得选，所以不存在什么『坏人不需要对自己的罪行负责这种事情』。

甲：怎么讨论讨论就变成宿命论了？

乙：什么是宿命论？

甲：就是那种一切都被命运安排好，任何人都没有选择的自由，只能被命运摆布的世界。

乙：不对啊，许多人不都在努力改变自己的生活么。

甲：但无论他们怎么努力，结果都是一样的，所以是白费功夫。

乙：努力的结果是宿命，努力本身也是宿命，既然都是宿命，当然谈不上什么『白费功夫』。如果努力本身不是宿命，是可以选择的行为策略，那么努力的结果怎么会是宿命？难道命运只安排你最终的归宿而不安排你之前的经历么？

甲：……恩，好像确实如此，命运不仅安排人生的归宿，也限制人生的经历。但宿命总是一个令人不爽的东西。

乙：宿命至少让你对失去自由不爽了。但我看不出你在谈到宿命论之前和谈到宿命论之后有什么区别，为什么经过这么一个短短的思考你就『突然间』失去了自由？

甲：……并不是我『突然间』失去了自由，我从来就没有过自由，但之前我以为自己有自由，那只是一种幻觉。即使是现在我跟你所说的每一句话也都是安排好的。

乙：既然如此，你的现状并没有什么真的改变，为什么你要变得沮丧？当然，你可以说你变得沮丧也是命运安排的，但我的命运就没有安排我对这种事情感到沮丧，而且你也并不能精确预测十分钟以后命运是否会安排你继续沮丧下去。

甲：你说的对，我不知道命运是如何安排的，说不定十分钟以后我的状态会有所改变。虽然命运是决定了的，但我并不能准确的预测我的命运。

乙：没错，即便一切都已经决定，也不意味着任何人有能力预测它。如果你能够预测命运，那么你这样做也不过是被命运安排好的，至于你的预测结果是否符合真正的命运，照样是由命运决定而不是你来决定的。

甲：说不定有人不是被命运安排的，他们可以预测。

乙：如果有人可以预测，并且可以把结果告诉你，那么至少你关于未来的知识就不是被命运安排好的。否则即便有人可以预测也无法改变你的知识，因此对于你这种被命运安排的人来说，你的知识也是被安排好的。而如果你的知识改变了，除非你的行为从此完全不听你的控制，否则你的行为就会因为你知识的改变而改变。

甲：……

September 11th, 2010 | 荒唐 | Categories: 哲学 | Comments: No Comments

对话——人生的意义#非正常人类对话系列#

甲：人生的意义是什么？

乙：谁的人生对谁的意义？

甲：不管谁的人生，也不管对谁的意义。

乙：那你先告诉我x+3等于几。

甲：x等于几？

乙：不管x等于几。

甲：x+3等于x+3。

乙：那人生的意义就是人生的意义。

甲：靠。

乙：张三的人生对李四的意义，取决于李四认为张三的存在对自己有什么价值，也就是张三的存在能够在什么程度上满足自己的意愿。

甲：比方说呢？

乙：比方说张三是李四的孩子，李四认为张三是自己生命的延续，那么张三对李四的意义就是延续生命。再比方说张三是李四的偶像，让李四觉得这个世界更加精彩，那么张三对于李四的意义就是让世界更加精彩。再比方说张三是李四的亲戚朋友，让李四觉得自己不孤独，那么张三对李四的意义就是让李四感觉到关怀和温暖。再比方说张三是李四的敌人，让李四感到仇恨，那么张三对李四的意义就是仇恨的对象……

甲：好了，例子够多了。但我还是想知道，意义的对象必须是一个人么？比方说我能否谈论我的人生对这个世界的意义？

乙：你这个世界是什么意思？是指人类社会，还是指整个宇宙？

甲：随便什么吧。

乙：你能告诉我这个『世界』它有什么意愿？

甲：不知道，应该没有吧。

乙：如果没有任何意愿，自然也就不可能在任何程度上实现意愿，谈论任何东西对一个没有意愿的对象的意义都是有语病的。

甲：……看来的确如此。如果是对人类社会的意义呢？人类社会在某种程度上是有意愿的吧？

乙：人类社会的意愿是什么，这本身就是一个没有明确答案的问题。比方说有人认为权力颠峰的人的意愿可以代表人类社会的意愿，或者舆论导向代表人类社会的意愿，或者认为延续种群基因才是人类社会的意愿，或者认为每一个人的意愿全部集合起来就是人类社会的意愿……，不过我们不必关心具体的答案，随便选择哪一种作为人类社会的意愿，你都可以回答某个人对这个意愿的实现有什么价值。当然，也有人认为人类社会不是一个可以谈论『意愿』的对象，因此无法谈论任何东西对人类社会的意义。

甲：……恩，我明白了。不过看来谈论一个人对人类社会的意义也没什么意思，就算我的人生对这个世界有意义，也不等于对我自己也有意义。我更想知道我的人生对我自己的意义。

乙：你的人生对你自己的意义，这个问题的具体答案只有你自己才知道。如果你想实现任何意愿，前提条件都是你活着——如果死后不能实现任何意愿的话——，于是你活着对于你实现任何意愿都是必要条件，在这个角度上你的人生对你自己的意义就是它是你实现任何意愿的必要条件。如果你压根就不想活着也没有任何其他意愿，那么你的人生对你就没什么意义。

甲：不过我想知道的恰恰是我为什么活着，这似乎陷入了一个死循环：因为人生有意义我才想活着，但只有我想活着人生才能有意义。反过来不想活着的话人生也就没有意义，人生没有意义还何必想要活着呢？严重纠结……

乙：你确定是『因为人生有意义』你才想活着么？

甲：难道不是么？如果没有意义我为什么要活着？

乙：那么，如果最终的答案就是『人生就是没有任何意义』，你会毫不犹豫立即自杀么？

甲：……应该不会吧，但即便不想活着，也没那么想死吧？

乙：但问题是为了活着你要做很多事情啊：打工赚钱、买米买菜、洗衣做饭、睡觉起床……你不想活着干嘛要为了活着做这些事情？

甲：……吃饭是因为饿了，睡觉是因为困了，虽然我并不想活着，但饿了困了毕竟是件不舒服的事情，而且自杀要忍受巨大痛苦吧，我毕竟还不愿意忍受那么大的痛苦。

乙：看看，上面这些理由即便不是你活着的全部原因，也至少是部分原因，为了避免『不舒服』你还是选择了继续活着。我再问你：如果人生没有意义，而且有一种自杀的方法非常方便且没有痛苦，你会毫不犹豫立即自杀么？

甲：……可能会的，我有时候觉得活着也挺累的……

乙：既然活着挺累的，你压根又不想活着，那么你的最佳策略是研究一下怎么死才能方便无痛苦，并且付诸实现才对，你去做了么？

甲：……说实话我还真的研究过，但我总觉得不甘心。如果人生是有意义的，死了岂不是白死了。活着可以做许多选择，至少还可以选择死，但死了就万劫不复了。

乙：看看，又找到一条让你活着的原因：『有机会做选择』，你现在已经有了若干条活着的理由了。

甲：……算是吧，但我总觉得这些理由还不够充分……

乙：怎么不充分，这些理由一直让你活到现在。

甲：难道人活着仅仅是为了吃喝拉撒睡娶媳生子并且有选择可以做么？这样的人生跟猪狗有什么不同？

乙：这完全是你的自由。你可以仅仅为了这些意愿活着，你也可以不仅仅为了这些意愿活着，关键是你有什么意愿。另外，干嘛要瞧不起猪狗呢？你不愿意就不那样活好了。

甲：不那样活着还能怎样活着呢？

乙：除了吃喝拉撒睡，你还有其他的爱好么？比方说看电影电视、听音乐、打球、跑步、开卡丁车、美食、泡妞、赌博、偷东西、杀人放火搞破坏、反人类……

甲：靠，反人类都行啊。确实还有些其他的爱好，但我不知道这些爱好又有什么意义。

乙：反人类行不行是另一个话题。这些爱好的意义不就是让你感到满足么？跟吃喝拉撒睡一样，既然你可以为了舒服而吃喝拉撒睡，干嘛不能为了满足而追求这些爱好呢？

甲：我有点明白了，你是不是说人生的意义不是个好问题，我想知道的实际上是我到底想要什么，我应该怎么做。

乙：没错，这才是恰当的问题。而且获取这两个问题的答案，别人只能提供帮助，只有你自己才能做出判断。

甲：我想要的东西很多，我能得到的却很少，这让我很苦恼。

乙：所以你得弄清楚自己真正想要的到底是什么，做出取舍。比方说你喜欢看热闹，更深的原因可能是为了满足好奇心，而满足好奇心未必只能通过看热闹这一个途径。

甲：我明白了，你的意思是说某些需求可能仅仅是为了满足更深层的需求，对吧？

乙：是的。追溯自己每一个动机的根源，也是一种内省的方式。

甲：如果这样追溯下去，会不会又一次陷入无限循环？

乙：有些需求并非源于更深层次的需求，比方说食欲性欲求生欲好奇心之类，这些需求并非以满足其他需求为目标，这些需求可以称之为原始欲望。但这是另一个话题了。

甲：……看来的确如此。如果人生就是为了满足那些欲望，那吸毒岂不是更加直接快速？

乙：你会去做么？为什么？

甲：我不会，那是罪恶的，我不想过那样的生活。

乙：你如果已经开始吸毒，你的想法说不定会改变。

甲：嗯……可能吧，但我现在并不想过那种生活的。

乙：是的，其实你根本不需要知道已经吸毒之后想法是否会变，你只需要知道你现在并不想要过那种生活，就好像你根本不需要知道你死后还想不想活着，你只需要知道你现在想要继续活着。

甲：确实如此，但选择不吸毒的理由仅仅是这些么？

乙：你当然可能有许多其他的更加具体的理由，但你的意思是不是想找到无论在什么情况下都坚决拒绝吸毒的理由？

甲：这难道也有问题么？

乙：如果你病入膏肓，勉强维持生命却必须忍受比千刀万剐还要巨大的痛苦，什么事情也做不了，你也宁可这样痛苦地死去也拒绝使用毒品来在生命的最后一刻得到解脱么？

甲：……这我还真没考虑过，这种情况下我可能不会拒绝毒品吧，不过这也太极端了。

乙：无论在什么情况下都坚决拒绝毒品更加极端。

甲：……看来确实如此。我原来误以为毒品是万恶的，任何人任何情况下都绝不应该沾的东西。

乙：你原来的想法也未必是错的。

甲：我不明白，你好像自相矛盾了。

乙：因为脱离评判对错的标准谈论对错就跟脱离关心意义的主体谈论意义一样，而这又是另一个话题了。

甲：靠，你又来了～～

September 10th, 2010 | 荒唐 | Categories: 人生, 哲学, 心智 | Comments: No Comments

有限的人生能飞多远——随手算算

给你一艘飞船，你在有限的人生中能够探索多么遥远的未知世界呢？

如果你了解一点狭义相对论，你可能会回答能够探索的距离不会超过光在人生中走过的距离，因为光速是速度的极限。且慢，别忘了你自己就是旅行者，你能够飞多远取决于你亲身经历的时间（称为固有时间：proper time），而不是取决于你在某个惯性系中经历了多长时间。

当你相对惯性系 $S$ 以速度 $\beta$ （ $\beta=v/c$ ，今后如果不加说明，我们全部采用 $c=1$ 单位制，这种单位制下 $\beta$ 和 $v$ 完全相等）前进的时候，你的固有时间 $d\tau$ 跟惯性系 $S$ 的时间 $dt$ 的关系是 $d\tau=\sqrt{1-\beta^2}\;dt$ 。

首先，我们必须给出固有加速度恒定的情况下 $\beta$ 对 $t$ 的函数关系，注意， $\beta=a t$ 是完全错误的，这是非相对论的匀加速运动的公式。相对论的速度变化比较复杂，为了避免过于冗长的计算，我们采用固有速度（proper velocity）的绝对值：快度 $\eta$ （rapidity），与 $\beta$ 的关系是：

$\beta=\tanh(\eta)$

采用快度 $\eta$ 的好处是可以它直接相加。相对论的速度相加公式很繁琐，但你可以把若干个要相加的速度都变成相应的快度，把这些快度简单的加起来，然后再变换回速度，就可以得到正确结果。对于在 $t=0$ 时刻开始的以恒定固有加速度a的加速过程，刚好有跟经典力学中匀加速运动类似的公式：

$\eta=a \tau$

于是，现在就可以计算惯性系 $S$ 中的时间 $t$ 和做恒定固有加速运动的固有时间 $\tau$ 的关系了（具体的积分运算过程略，有兴趣的同学可以用Mathematica验证一下）：

$\begin{array}{ll} \displaystyle t&\displaystyle=\int\limits_{0}^{\tau}\frac{d\tau'}{\sqrt{1-\tanh(a \tau')^2}}\\ &\displaystyle=\frac{\sinh(a\tau)}{a} \end{array}$

$\displaystyle\tau=\frac{\sinh^{-1}(a t)}{a}$

经过固有时间 $\tau$ ，做恒定固有加速运动所达到的速度是 $\beta=\tanh(a \tau)$ ，所走过的路程是：

$\begin{array}{ll} \displaystyle s(\tau)&\displaystyle=\int\limits_{0}^{t(\tau)}\beta(x)dx\\ &\displaystyle=\int\limits_{0}^{t(\tau)}\tanh(sinh^{-1}(a x))dx\\ &\displaystyle=\int\limits_{0}^{t(\tau)}\frac{a x}{\sqrt{1-a^2 x^2}}dx\\ &\displaystyle=\frac{\sqrt{1+a^2 t(\tau)^2}-1}{a}\\ &\displaystyle=\frac{\cosh(a \tau)-1}{a} \end{array}$

当 $a \tau$ 很大的时候， $\displaystyle\frac{\cosh(a \tau)-1}{a}\rightarrow\frac{\exp(a \tau)-2}{2 a}$

也就是说，你可以到达的距离是你寿命的指数函数。

为了有一个感性认识，我们计算一下当你以地表的重力加速度 $g$ 持续加速，花一段时间能够到达多远的地方： $g=9.8m/s^2$ ，转换到 $c=1$ 单位制， $1s=3 \times 10^8m$ ： $g=9.8m/s^2=3.27\times 10^{-8}/s=1.0323/y$ （很巧，地球表面重力加速度g的数值差不多刚好是一倍光速每年），于是：

$\begin{array}{ll} \displaystyle\frac{\cosh(a \tau)-1}{a}&\displaystyle=\frac{\cosh(1.0323/y \times 1y)-1}{1.0323/y}\\ &\displaystyle=0.5636y \end{array}$

你只需要经历1年，就可以到达0.5634光年远的地方，只需要10年，你就可以到达14684光年的地方，如果你能活到100年，就可以到达 $3.167\times 10^{44}$ 光年的地方，现代宇宙学所估算的宇宙半径也不过上百亿（ $10^{10}$ ）光年。

我们现在再来算算，如果你的飞船总质量为 $m$ ，采用反物质发动机，将所消耗掉的质量全部转化为光子发射出去，利用光子的反推实现加速（这是理论上最高效的推进方式），这种情况下想要让你的飞船产生大小为 $a$ 的固有加速度，你需要以多块的速度消耗飞船上的物质。

由于采用了 $c=1$ 单位制，光子的动量和能量是相等的，消耗掉的质量所得到的能量跟所消耗的质量也是相等的。为了让质量为 $m$ 的飞船达到加速度 $a$ ，那么需要的力 $f=m a$ ，而推力 $f$ 完全由单位时间内喷射的光子动量提供： $f=dp/d\tau=dE/d\tau=-dm/d\tau$ 。于是 $-\frac{dm}{m}=a\;d\tau$ ，因此，当飞船质量为 $m$ 时，单位时间内所喷射的质量占总质量的比值恰好由 $a$ 决定。当飞船质量 $m$ 逐渐变小的时候，所需的推力 $f$ 也随之变小，可以算出飞船任意时刻的剩余质量随着 $\tau$ 的变化： $m(\tau) = m_0 \exp(-a \tau)$ 。所以，用效率最高的反物质发动机，1年以后飞船的剩余质量为最初的2.808分之一，10年以后飞船的剩余质量为最初的30424分之一，100年以后飞船的剩余质量只有最初的 $6.795\times10^{44}$ 分之一。如果飞船是由氢构成的，那么出发时总质量一千万亿吨（相当于地球大气总质量的1/5，跟喜马拉雅山的总质量差不多），100年之后也只能剩下一个氢原子的质量了，如果你希望100年后剩下一个人那么大的质量，那么出发时大概需要上百个银河系的总质量。

September 8th, 2010 | 荒唐 | Categories: 心得, 物理 | Comments: No Comments

吃苹果游戏和简单回合制游戏的通解

问题：
有20个苹果。
两个人轮流吃，可以吃一个，也可以吃半个。
吃半个的时候，可以吃原来就是半个的，也可以把一个完整的吃掉一半，也就是说可以有很多半个的苹果。
吃一个的时候，只能吃完整的一个。
没有其他选项。
最后吃苹果的人输。

请问，先吃还是后吃的有必胜的策略？这个必胜策略是什么？

答案：
后手有必胜策略。开始的时候先手怎么吃，后手就怎么吃，换言之后手总是设法保持剩下的整苹果和半苹果都是偶数即可。但当剩下的整苹果刚好只有两个的时候，肯定轮到先手吃，而后手此时不能跟先手学。如果先手吃掉一个整苹果，后手就把最后一个整苹果吃掉一半，让半苹果数量变成奇数。如果先手把一个整苹果吃掉一半，那么后手就吃掉最后一个整苹果，保持半苹果是奇数个。由于此时剩下奇数个半苹果，只能轮流吃，后手必胜。

这个问题的答案并不很难找到，通过倒推的方法很容易解决。但对于这类问题，有没有通用的解法呢？
现在就给出一个通用的解法：

通解：

确定游戏的完整状态（或者说局面）参数。比方说上面题目的完整状态参数就是(m,n,p)，m是整苹果的个数，n是半苹果的个数，p是此时由谁行动。
游戏的行动规则确定了状态的迁移规则，或者说从某个状态出发可以到达哪些状态。比方说上面题目从(m,n,p)出发只能到达(m-1,n,~p)——吃一个整苹果、(m,n-1,~p)——吃一个半苹果、(m-1,n+1,~p)——吃半个整苹果，~p表示轮到对方行动。
游戏的初始规则确定了状态空间的出发点。
游戏的获胜规则确定了哪些状态是直接被判定为某一方获胜的。比方说上面问题中(0,0,p)意味着p获胜。在这些状态上，哪个玩家获胜，那么这个状态本身对于这个玩家来说就是有必胜策略的状态（废话，这个状态玩家p都已经获胜了那么p在该状态上当然是有必胜策略的）。
最后一步就是从这些已知的必胜状态出发，递归地确定其他的状态是哪个玩家有必胜策略的状态。如果对于一个玩家来说，根据行动规则某个轮到自己行动的状态存在到达某个自己必胜的状态的行动选择，那么该点对于自己来说也是必胜状态，于是可以递归地将所有的状态都标记上是哪一方必胜，初始状态也会被标记，因此就可以确定初始状态哪一方有必胜策略。

上述解法原则上可以寻找任何完全信息的确定性的回合制的游戏的必胜方和必胜策略。完全信息意思是任何一个回合中，每一个玩家对游戏的局面都有完全的信息，因此不包括桥牌这种不知道对手手中有什么牌的游戏。确定性意思是轮到任何一个玩家行动的时候他可以做出完全确定的行动，因此不包括飞行棋之类需要掷骰子决定如何行动的游戏。回合制意思是参与游戏的若干玩家是按照确定的规则轮流行动的，行为决策是离散的，因此不包括需要连续不断地做行为决策的游戏。类似围棋象棋五子棋跳棋（可以是多方跳棋）的游戏原则上都可以用上述解法寻找必胜方和必胜策略。只不过对于大部分流行的棋类游戏，上述方案会过于庞大以至于无法实际应用。但对于前面这种可以用于做智力题的完全信息确定回合制游戏，用上述通用解法大都可以迅速找到必胜方和必胜策略。

现在以前面的问题为例来说明这个通用解法。由于规则是两个人交替行动，所以(m,n,p)里面的p可以省略，用(m,n)代表状态就可以了，于是状态空间就变成了二维平面上的格点空间。而游戏的行动规则决定了从一个格点出发可以到达哪些格点。注意，由于取消了参数p，所以(0,0)状态无法确定谁胜谁负，但只有一个半苹果的状态(0,1)显然是后手必胜，因为先手只能吃掉这半个苹果而输掉游戏。另外，只有一个整苹果的状态(1,0)显然是先手必胜，但这一点可以通过(0,1)是后手必胜来导出，因此是可有可无的。有了这一个确定的格点，其他所有的格点先手还是后手有必胜策略都可以确定了：对于任何一个格点S，如果从S出发能够到达的所有格点全都是先手有必胜策略的格点，那么S就是后手有必胜策略的格点（因为后手在下一步变为先手）。否则，如果从S出发能够到达的格点之中至少有一个是后手有必胜策略的格点，那么S就是先手有必胜策略的格点（因为先手可以选择进入这个后手必胜的格点，自己同时变成后手）。

上图中，直接确定了(0,1)、(1,0)两个画圈的点的必胜方和必胜策略。图中选了几个典型的点示范了其他点的颜色是如何确定的：凡是从该点出发只能到达绿色点的点都涂成红色，凡是从该点出发至少有一个目标点是红色的点都涂成绿色。从两个画圈的点出发（其实只从(0,1)出发就够了），可以递归确定所有点的颜色。只需要做几步就可以发现规律得到答案。

September 1st, 2010 | 荒唐 | Tags: 博弈, 游戏.
Categories: 数学, 灵感, 算法 | Comments: No Comments

« Previous Page — Next Page »