T*******x
发帖数: 8565 | 1 集合A有4个元素，集合B有2个元素。集合C是A到AXB（笛卡尔积）的函数的集合，并且
每个函数满足：每个分量都是满射。求集合C的元素个数。 | S*E
发帖数: 3662 | | T*******x
发帖数: 8565 | 3 挺多，不好数。
【在 S*E 的大作中提到】
: 数数
| T*******x
发帖数: 8565 | 4 这个问题可以变化一下，就更难了：
集合B不变，A变成两个，A1和A2，A1有两个元素，A2有三个元素。C为A1XA2到A1XA2XB
的函数的集合，每个分量都是满射。求C中元素个数。
【在 T*******x 的大作中提到】
: 集合A有4个元素，集合B有2个元素。集合C是A到AXB（笛卡尔积）的函数的集合，并且
: 每个函数满足：每个分量都是满射。求集合C的元素个数。
| T*******x
发帖数: 8565 | 5 给个经验公式：
n! (2^n-2)
其中n为集合A的元素个数，集合B永远是固定的。
这个公式我没有证明。
【在 T*******x 的大作中提到】
: 集合A有4个元素，集合B有2个元素。集合C是A到AXB（笛卡尔积）的函数的集合，并且
: 每个函数满足：每个分量都是满射。求集合C的元素个数。
| w**********5
发帖数: 1741 | 6
2^4-2 =14
【在 T*******x 的大作中提到】
: 集合A有4个元素，集合B有2个元素。集合C是A到AXB（笛卡尔积）的函数的集合，并且
: 每个函数满足：每个分量都是满射。求集合C的元素个数。
| T*******x
发帖数: 8565 | 7 这个问题出自图灵机。图灵机的一个变形，是一条纸带，一个扫描打印头，纸带上可以
书写的符号的集合就是本题集合A。扫描打印头可以向左或向右移动，这两个动作是集
合B。集合C中每一个函数，就是图灵机的一个程序。任意给定纸带上的初始输入，程序
就可以开始运行。
不过这里要求每个分量都是满射是不合理的。后面那个把A分解为A1，A2，然后要求每
个分量为满射，是合理的。这就是标准图灵机的定义了，A1为内部状态数，A2为纸带符
号，只有两个，0和1。这样分解一下，集合C的元素就多多了，也就是说图灵机的合理
程序就多多了。
【在 T*******x 的大作中提到】
: 集合A有4个元素，集合B有2个元素。集合C是A到AXB（笛卡尔积）的函数的集合，并且
: 每个函数满足：每个分量都是满射。求集合C的元素个数。
| T*******x
发帖数: 8565 | 8 A1是纸带符号集合，A2是图灵机内部状态集合，B是左右移动。A1只有两个符号，0和1
。A2假设有3个内部状态。那么每一个图灵程序，是一个(2,3)->(2,3,2)的函数。总共
有多少个函数呢？有12^6个函数，大概3个million。其中每个分量都是满射的，我数了
一下，大概2个million多一点。也就是说实际上大部分程序都是合理的。而且一个图灵
程序可能不一定要求每个分量都是满射，比如下面这个，著了名的busy beaver程序：
https://en.wikipedia.org/wiki/Turing_machine#Turing_machine_%22state%22_
diagrams
这个busy beaver实际上是4个内部状态 -- 停机算一个状态的话。也就是(2,4)->(2,4,
2)的一个函数。这样的函数有16^8个，4294967296个，我的个妈呀，4个billion。把这
个busy beaver表示出来，它是这个样子：
{
(0, 0): (1, 1, 1),
(0, 1): (2, 1, 0),
(1, 0): (0, 1, 0),
(1, 1): (1, 1, 1),
(2, 0): (1, 1, 0),
(2, 1): (3, 1, 1),
(3, 0): (3, 0, 1),
(3, 1): (3, 1, 1)
}
编码一下，它是第4260786855号程序。
A1XA2XB
【在 T*******x 的大作中提到】
: 这个问题可以变化一下，就更难了：
: 集合B不变，A变成两个，A1和A2，A1有两个元素，A2有三个元素。C为A1XA2到A1XA2XB
: 的函数的集合，每个分量都是满射。求C中元素个数。
|
|
