首页 > 其他分享 >关于FGH

关于FGH

时间:2023-12-07 17:36:47浏览次数:26  
标签:24 ... FGH 关于 sup alpha omega 序数

虽然是英文但是讲的不错,稍微翻译一下罢(虽然已经有挺多人写过这个了)
网站
说起来发明FGH这个标尺的确实是神,简洁明了

前置知识

超运算

这倒是非常自然的想法
若将加法看作第一级运算,乘法看作第二级运算,乘方看作第三级运算,如何继续推广呢?
我们观察以下乘法和乘方是怎么定义的

\[a*b=a*(b-1)+a\\ a^b=a^{b-1}*a\]

那么我们定义第\(n\)级运算(边界显然,故略去)

\[f_n(a,b)=f_{n-1}(f_n(a,b-1),a) \]

对角化

我们考虑一个函数\(x^2\),怎么将它变大(在增速上)?
一种简单的方法是变成\(x^3\),这样它的增速就变成\(O(n^3)\)了
然而把指数换掉也终究只是多项式级,即使是\(O(n^{100})\)远远比不上指数级的\(O(2^n)\)
于是这启发我们把指数也换掉,变成\(x^x\),于是它的增速比指数级还高了

一般的,我们把对一个二元运算中的两个元设置成同一个变量的操作称为对角化
例如\(x+x>x+c,x*x>x*c,x^x>x^c\)
注意对角化是一个非常强的操作,在我们卡壳的时候常常可以用这个突破

一些基础的定义

序数与基本列

从集合的角度可以定义自然数\(0=\{\},1=\{0\}=\{\{\}\},2=\{0,1\}=\{\{\},\{\{\}\}\}\)
于是我们定义后继\(n+1=n\cup\{n\}\),由归纳公理我们可以定义出自然数集
然而定义出的这些数终究是常数,有没有办法让它变化,或者说比任何常数都大?


于是我们开启了序数的大门
我们定义极限序数\(\omega=\{1,2,3,...\}\),这个序数比先前定义的任何常数都大
于是我们定义:序数(ordinal number) \(\alpha=\sup\{\beta|\beta<\alpha\}\)
后继序数\(\alpha+1=\alpha\cup\{\alpha\}\)
我们称\(\{\beta\}\)为序数\(\alpha\)的基本列,例如\(\omega\)的基本列为\(\{1,2,3,...\}\)
于是我们知道\(\omega+1=\{1,2,3,...,\omega\}\)
将其不断累加,我们得到\(\omega+\omega=\sup\{\omega+n\}=\sup\{1,2,3,...,\omega,\omega+1,...\}=\sup\{\omega+1,\omega+2,...\}\),我们将其记为\(\omega2\)


注意
序数运算不满足交换律
例如\(1+\omega=\sup\{1+n\}=\sup\{n\}=\omega\),中间两个等号相等是因为两个基本列的上界是一样的
例如\(2\omega=2+2+...+2=\sup\{2+n\}=\sup\{n\}=\omega\),第一个等号可以用归纳法证一下
有一种简单的办法是数括号层数


于是我们继续累加得到\(\omega2+\omega=\omega3\),一直加到\(\omega\omega\),记作\(\omega^2\)
\(\omega^2\)的基本列是\(\{\omega,\omega2,\omega3,...,\}\)
继续叠可以一直叠到\(\omega^\omega=\{\omega,\omega^2,\omega^3,...\}\)

F(ast)G(rowth)H(ierarchy) 快速增长层级

FGH的想法尽管很自然,但我大概想不到(
FGH将序数映射为定义在自然数上的单元函数,定义:

\[\begin{split} f_0(n)&=n+1\\ f_{\alpha+1}(n)&=f^n_\alpha(n)=f_\alpha(f_\alpha(...f_\alpha(n)))\\ f_\alpha(n)&=f_{\alpha[n]}(n) \end{split}\]

其中\(\alpha[n]\)表示基本列中的第\(n\)项


然后是大数不可不品的一大堆例子爆算

\[\begin{split} f_0(n)&=n+1\\ f_1(n)&=f^n_0(n)=n+1+...+1=2n\\ f_2(n)&=f^n_1(n)=n*2*...*2=2^nn\\ f_3(n)&=f^n_2(n) \end{split}\]

到了\(f_3\)的时候已经不能用乘方展开了,但是显然大概在第四级运算的级别
一般的,\(f_{n-1}\)大概在第\(n\)级超运算的级别
然后我们看看当我们用上极限序数会发生什么


\[\begin{split} f_\omega(3)&=f_3(3)\\ &=f_2(f_2(f_2(3)))\\ &=24*2^{24}*2^{24*2^{24}} \end{split}\]

是否觉得不过如此?

\[\begin{split} f_{\omega+1}(3)&=f_\omega^3(3)\\ &=f_\omega(f_\omega(f_\omega(3)))\\ &=f_\omega(f_\omega(f_3(3)))\\ &=f_\omega(f_\omega(f_3(3)))\\ &=f_\omega(f_\omega(24*2^{24}*2^{24*2^{24}}))\\ &=f_\omega(f_{24*2^{24}*2^{24*2^{24}}}(24*2^{24}*2^{24*2^{24}})) \end{split}\]

仅仅将\(\omega\)换成\(\omega+1\)效果就恐怖如斯了
典中典的葛立恒数\(G\)的增长率也就在这里

标签:24,...,FGH,关于,sup,alpha,omega,序数
From: https://www.cnblogs.com/123789456ye/p/17881847.html

相关文章

  • 如何搭建一套完整的智能安防视频监控平台?关于设备与软件选型的几点建议
    安防视频监控系统主要由前端摄像机设备、视频显示设备、视频存储设备、安防应用软件/平台以及其它传输、辅助类设备组成。一般来说,安防监控系统具有可扩展和开放性,以方便未来的扩展和与其他系统的集成。今天我们就来介绍一下,搭建一套完整的安防监控平台,应该如何选型?1、前端监控设......
  • 《Java编程思想第四版》学习笔记45--关于图标
    //:Faces.java//IconbehaviorinJButtonspackagec13.swing;importjava.awt.*;importjava.awt.event.*;importjavax.swing.*;publicclassFacesextendsJPanel{staticIcon[]faces={newImageIcon("face0.gif"),......
  • 关于浮点数误差以及四舍五入
    https://blog.csdn.net/Xavier_97/article/details/126931927由于很玄学,我们考虑统一使用库函数round和自己手写round来实现最终输出整数的四舍五入和小数保留k位的四舍五入#include<iostream>#include<cmath>usingnamespacestd;intmain(){doublea=1.4999999......
  • 关于uniapp打包APP自定义基座调试,遇到首页同意网络权限后白屏问题
    解决方案:1、在App.vue文件中,onShow生命周期内添加一段代码,检测是否同意使用互联网权限:uni.onNetworkStatusChange(function(res){ console.log('onNetworkStatusChange',res); if(res.isConnected){ setTimeout(()=>{ uni.reLaunch({ url:'/pages/......
  • 关于类图中的箭头含义
    UML类图中各箭头表示总结1、泛化2、实现3、依赖4、关联5、聚合6、组合在UML类图中,箭头关系是用来表示类之间的关系的。箭头关系的种类有以下几种:1、泛化泛化:表示类之间的继承关系。箭头从子类指向父类。箭头:实线空心三角箭头如下图所示,Person为父类,Student和Professor为子类 ......
  • 《Java编程思想第四版》学习笔记44--关于按钮组
    //:ButtonGroups.java//Usesreflectiontocreategroupsofdifferent//typesofAbstractButton.packagec13.swing;importjava.awt.*;importjava.awt.event.*;importjavax.swing.*;importjavax.swing.border.*;importjava.lang.reflect.*;publicclassB......
  • 关于Winform+KitWare.VTK+PCL处理3D点云文件的编译环境
    最近项目需求,在网上找了一个处理3D点云文件的源码,但是发现无法编译,研究了下原来是电脑环境问题,必须配置一个PCL库的环境才能使用,下面进入正题。首先需要安装PCL环境,可以通过vcpkg安装(因为我没有成功,所以请自行查找),我是一直卡在装载pcl环节失败,网上搜了很多解决方法,包括重装VS英文......
  • 关于Windows更新失败(0x80070005)
    记录一下近几日关于Windows更新失败的处理(0x80070005)我的台式机配置:系统:Win10专业版(安装有半年多,前几天更新了系统盘,通过diskgenius克隆硬盘后可以正常使用)处理器  英特尔[email protected]四核主板  华硕PRIMEZ270-A内存  48GB(金士顿DDR42400......
  • 关于java:Windows:如何获取所有可见窗口的列表,并将指定窗口置顶
    importcom.sun.jna.Native;importcom.sun.jna.Structure;importcom.sun.jna.win32.StdCallLibrary;importorg.apache.commons.lang3.StringUtils;importjava.util.*;publicclassBringToForeground{publicstaticvoidmain(String[]args){Bri......
  • 关于操作符的两道面试小题
    一.练习:编写代码:求一个整数存储在内存中的二进制中1的个数首先:看到这个题是首先应该想到整数在内存中存储的形式是二进制的补码其次:例如整数123,若想知道这个十进制数的个十百位都是什么,可以用123%10,或者用123/10;同理对于一个二进制数来说,若想知道它的每一位是0是1,只需让它%2或/2最......