25小说网 通过搜索各大小说站为您自动抓取各类小说的最快更新供您阅读!

【写在8月25日20:53,发布后发现上下标给我全滤了?,我调整一下,过会儿再看】

硬核程度:☆☆☆☆☆

涉及领域:计算理论

大标题:三种函数外加三种操作怎样解决所有可计算问题?为什么偏递归函数可以制造无限循环?

可能是全网最不报菜名、最不装比的解释。

以下开始:

首先,什么是可计算?

可计算就是指,有一个算法,我们把它交付给计算机后,计算机可以像执行一个函数一样,接受我们给它的输入,然后返回输出,这个输出就是我们想要的答案。

为了方便描述,先行约定一下数学符号。

假设我们有一个乘法器,叫做mult,它可以接受一对整数作为输入,把它们相乘后输出一个整数。

比如,输入(3,4)输出12

输入(6,2)输出12

输入(0,6)输出0

这时,我们把这些输入数对叫做domain,输出的一个数叫做codomain。如果我们用Z来代表全体整数集,那么这个平平无奇的乘法器就可以用数学符号表示为:

mult:Z^2→Z

中间的这个→表示这个mult是一个total function,也许可以称作“全函数”吧,意思是每一个domain里的输入,都能对应一个codomain里的输出。

与全函数相对应的是,是“偏函数”。对于偏函数,对于有些输入,它并不能给出输出。比如一个除法器,当我们给它(6,0)时,它输出不了任何东西。这个除法器可以表示为:

div:Z^2—Z

这里的单横线代表这是一个偏函数(其实应该用半箭头表示,但在这里打不出来)

好了,定义好符号之后,就可以清爽地描述我们的三种基本函数:后继函数、零函数、投影函数。

后继函数:succ:N→N,succ(x)=x+1,N代表自然数集。我们给它2,它输出3;给它3它输出4。总之就是往上+1.

零函数:zero:Nn→N,zero=0。不管给它什么,它都输出0.

投影函数:projn:Nn→N,projin(x1,...,xn)=xi。它接受长度为n的输入,输出第i个自然数。比如,proj22(1,3)=3。

好了,盖大楼的砖块一共就这么三种,接下来把它们组合在一起就行了。

我们定义一个叫“组合”的函数f,它的功能是把n个函数组合在一起:

f:Nn—N

具体的,如果每一个被组合的函数g都可以接受同一组参数(x1,...,xm),那么组合n个g函数的操作可以被表示为:

f·[g1,...,gn]:Nm—N

展开为:

f·[g1,...,gn](x1,...,xm)=f(g1(x1,...,xm),...,gn(x1,...,xm))

举个栗子:

我们构造一个函数one,one(x)=1,即:不论给它什么输入,它都输出为1,那么:

one(x)=succ(0)=succ(zero(x))

即:succ·[zero]=one

验证一下:

succ·[zero](x)=succ(zero(x))=succ(0)=1

succ和zero两个基本函数组成了我们要的one,完美。

如果栗子再复杂一点,我们想要一个加法器add,add(x,y)=x+y,怎么用那三种基本函数组合?

也很简单,从具体输入入手:

add(3,2)=succ(add(3,1))=succ(succ(add(3,0)))=succ(succ(3))

似乎只需要组合多个后继函数就可以了呢。

当然,这里面有一个毛病,在于我们在没有定义好add的前提下,先入为主地认为add(3,0)=3.

所以我们不能认为自己就这么简单地构造了add,只能退而求其次地得到以下关系:

add(x,y+1)=succ(add(x,y)),这个式子是十分严谨的。

更具体地,要想算出add(x,y+1),就要知道add(x,0)=x,我们称add(x,0)=x为基准条件;add(x,y+1)=succ(add(x,y))为递归条件。

看起来就差临门一脚了,只要我们能用三种基本函数构造出add(x,0)=x,就能得到add(x,y+1),也就能构造出我们想要的加法器。

也很显然,add(x,0)=x=proj11

于是,我们的加法器有了。

这种看起来很像左脚踩右脚登天的构造方式叫做“原始递归”,它的定义是这样的:

基准函数f:Nn—N

递归函数g:Nn+2—N

使用f和g的原始递归h=pn(f,g):Nn+1—N

对于h:

基准条件:h(x1,...xn,0)=f(x1,...,xn)

递归条件: h(x1,...,xn,y+1)=g(x1,...,xn,y,h(x1,...,xn,y))

回到我们的加法器add:

add:N2→N

add(x,y)=x+y=p1(f,g)

基准条件:add(x,0)=f(x)=proj11

递归条件:add(x,y+1)=g(x,y,add(x,y))=succ(add(x,y)),g=succ·[proj33]

add=p1(proj11,succ·[proj33])

完美无瑕。

类似地,乘法器mult=p1(zero,add·[proj13,proj33])

前继函数,减法器等等基本运算都可以据此定义,只需要proj,zero,succ三种原始函数和组合·,原始递归p这两种基本操作。所有完全函数都可以据此构造。

那么“偏函数”呢?

构造偏函数还需要额外的一个操作:最小化。

如果我们有一个函数f:N^n+1—N (这里^代表上标,虽然不好看,但实在是敲得太麻烦没有耐心了),具体的f(a1,...an,x),其中a1,...an是固定参数,x是可变参数。

那么最小化操作为:μ^nf:N^n—N它会找到给它输入的n个参数里,最小的一个,并输出

比如f(5,4,3,2,1,0)=0

如果遇到重复参数,那么就输出第一个最小的。

比如f(5,4,3,2,1,1)=1

假设我们有一个投影函数长这样:

proj21:N2—N (proj21中的2是上标,1是下标,下同,写不动摆烂了)

那么μ^1proj21:N—N

举个栗子:

假如我们给proj21弄一个最小化操作:μ^1proj21(1),其中1是固定参数。

如果我们穷举一下可变参数,就会发现:

proj21(1,0)=1

proj21(1,1)=1

我们永远也拿不到0,也就不存在最小化。也就是说,对于μ^1proj21而言,并不是每一个输入都对应一个输出,所以应用最小化操作,我们成功地构建了一个偏函数。

加减乘三种操作都在上文构建过了,现在就只剩下一个除了。除法div需要用最小化操作来构建。

假设,我们收到两参数a和b,想求a\/b,那么其中存在如下关系:

a=qxb+r,其中0≤r<b

我们想要的就是满足式子qxb≤a的最大的q,这等同于满足(q+1)xb>a,于是带余除法被转化为了一个最小化问题:

找到最小的q使其满足(q+1)xb>a

也就是构造一个函数f:N^3—N

f(a,b,q)=1如果(q+1)b≤a,=0如果(q+1)b>a

f(a,b,q)=lessthanequal(mult(succ(q),b),a)

f=lessthaneual·[mult·[succ·[proj33],proj32],proj31]

其中lessthanequal=iszero·sub

iszero=sub·[succ·zero,proj11]

sub是减法器

对f进行最小化操作即可得到我们想要的结果。

验证一下:

f(8,5,0)=lessthanequal(mult(1,5),8)=1不等于0,所以0不是输出。

f(8,5,1)=lessthanequal(mult(1,5),8)=0,最小,所以1是输出。

div(8,5)=8\/\/5=1没错,十分完美。

如果我们想计算一下8\/\/0:

f(8,0,0)=lessthanequal(mult(1,0),8)=1不等于0,所以0不是输出。

f(8,0,1)=lessthanequal(mult(2,0),8)=1不等于0,所以0不是输出。

无论我们给f(8,0,x)传入什么x,都找不到最小的x,所以div(8,0)=8\/\/0无解,符合现实。

如果把最小化操作运用在原始递归函数上,得到的新函数就叫做偏递归函数。

好了,现在加减乘除我们都有了,只要是可计算的算法,我们都能执行。

至于无限循环怎么制造出来,从μ^1proj21(1)和div的栗子都可以看出来,如果最小化操作找不到最小值,就永远不会给出输出,这相当于while语句的功能。

——————————————————

下一章是正常内容

25小说网推荐阅读:快穿女主:男神,撩不停快穿之男神恋爱秘籍踏破大千穿呀主神我从末世开始无敌小龙女快穿忙嗨,我是ChatGPT穿越奥特之塔艾斯特奥特曼快穿之龙套抢戏日常玄门妖王快穿空间界之男神请矜持位面之穿梭系统从捡到战争基地开始佛系女主在末世的强者之路末世,重生开启写轮眼我有一座恐怖屋有个公会叫呜呼电影黑科技宿主每天都在整幺蛾子尸命种子的长夜奥特:披着奥皮穿越发现都黑化了我为系统打工,系统赐我模拟怪谈异闻无限之爱萌魔法工业帝国末世生存,被我玩成了恋爱养成来自异世界的危机满级大佬在生存游戏里反派:主角女人太多,我薅不过来末日时钥鬼王传人追寻千年密码,揭开历史真相考古队的日子末日神弓手星空神猎球霸的黑科技系统我有一间练功室让你重生,没让你成人工智能超创无敌刺激进化壮士出川,我穿越到了抗战第一线港综世界大枭雄重选人生系统快穿小祖宗:反派大佬的娇娇宠天宇奇幻胖子的韩娱末世:圣母系统被无敌空间制裁了末世之邪恶炼金术士超级气运光环系统
25小说网搜藏榜:末日降临,我骗千亿大佬给我打工天人速递在影视世界里降妖除魔末世绿洲建造计划神级小商贩我真的不是精神病人末世御兽,开局薄纱小仙女前妻成为恶女后天天被发好人卡快穿:末世挣命日常无限之天赋掠夺红夜危机,异变后世界钢铁大亨盗墓之开局征服怒晴鸡精灵天王诸天祭祀囤好物资迎末世重生林平之神权指挥官末世重生:路人甲逆袭女主英灵机甲师全球创世:开局打造量子洪荒网游之剑震天下在希腊当岛主的日子快穿:时空任务系统阴阳鬼师她直播间通野蛮之地星战萌娘末世降临:我的末世是破解版末世之我有仙源无限之神座无敌进化巅峰快穿:男配稳住不要挂天赋炼制,造个变形金刚不过分吧星际孤幼院我的废品站,能回收太空战舰快穿之宿主正在渣化中全球迈入神话时代从科技论坛开始震惊全球争弦开局就送一头神宠死亡之最终试炼穿书女配之论户口本的重要性重回末世:我靠亿万物资躺赢天灾疯狂农场主站在食物链顶端的男人全球进化:开局觉醒SSS级主神黑光病毒:侵略多元宇宙快穿女神又黑化了我的专属梦境游戏美漫大镖客
25小说网最新小说:量子跃迁无尽冬日:女神们跪求进我家全民求生,获得D级人员模拟器末世超级指针我!丧尸母体,开启末世纪元末世降临:拿下邻妻和她闺蜜!请不要质疑多周目玩家开局丧尸末世,觉醒神级卡牌天赋文明余燃无限之武器大师的征途我就搞点小发明,鹰酱你慌什么?末世模拟器之开局釜山行孤站终末:灾变异闻录天灾末世:开局搜刮全球物资恶毒向导太娇媚,顶级哨兵抢破头人在废土,开局一只机械天使替身燃魂:破命绝杀极寒末世:开局一颗小太阳末世:收女仆,从高傲邻妻开始末世斗罗:教皇你怎么又又又怀了末世!别人求生,我收集婢女无机杀手:平行路口人在异界,抢到失联末日修仙:最后的希望获得高等文明传承,从地球开始崛末世:异界孤城末世歪厨懒人末日求生系统我要吃掉整个世界刃之星辰星际直播:华夏文明的逆袭之光我创造了18个人种末世当地主穿成兽世恶毒亲妈,全员跪求我宠末日!都重生了我舒服亿点怎么了快穿之拯救反叛魔神徒弟子嗣即虫群,我在废土播种恐怖丧尸罹灾之血疫人造英雄末世我在城郊别墅种田囤物平行世界偷心人抱歉,我真没想到自己这么强穿成末世文里的恶毒女配穿书后,向导在艰难求生!恶女稳定发挥,男主们为她沉沦重生者:末世生存战梦境互联末日回溯:破晓重生之战末世:我靠卖丧尸直播暴富