精华内容
下载资源
问答
  • 一切完备
    2021-01-18 15:03:04

    一、图灵完备的

    一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的。

     

    二、可计算的

    在可计算理论中,当一组数据操作的规则(一组指令集,编程语言,或者元胞自动机)满足任意数据按照一定的顺序可以计算出结果,被称为图灵完备(turing complete)。

    一个有图灵完备指令集的设备被定义为通用计算机。

    如果是图灵完备的,它(计算机设备)有能力执行条件跳转(“if” 和 “goto”语句)以及改变内存数据。

    如果某个东西展现出了图灵完备,它就有能力表现出可以模拟原始计算机,而即使最简单的计算机也能模拟出最复杂的计算机。

    所有的通用编程语言和现代计算机的指令集都是图灵完备的(C++ template就是图灵完备的),都能解决内存有限的问题。

    图灵完备的机器都被定义有无限内存,但是机器指令集却通常定义为只工作在特定的,有限数量的RAM上。

     

     

    https://zhidao.baidu.com/question/1801742013387194947.html

    更多相关内容
  • 证明一个距离空间是完备

    千次阅读 2021-10-17 22:09:04
    完备距离空间

    证明一个距离空间是完备的

    例题:

    S S S为由一切复数列
    x = { ξ 1 , ξ 2 , . . . , ξ n . . . } x=\{\xi_1,\xi_2,...,\xi_n...\} x={ξ1,ξ2,...,ξn...}
    组成的集合,在 S S S中定义距离为
    ρ ( x , y ) = ∑ k = 1 ∞ 1 2 k ∣ ξ k − η k ∣ ∣ 1 + ∣ ξ k − η k ∣ \rho(x,y)=\sum_{k=1}^{\infty} \frac{1}{2^k} \frac{|\xi_k-\eta_k|}{|1+|\xi_k-\eta_k|} ρ(x,y)=k=12k1∣1+ξkηkξkηk
    其中 x = ( ξ 1 , ξ 2 , . . . ) , y = ( η 1 , η 2 , . . . ) x=(\xi_1,\xi_2,...),y=(\eta_1,\eta_2,...) x=(ξ1,ξ2,...),y=(η1,η2,...).求证 S S S是完备的距离空间。

    第一步,先证 S S S是一个距离空间:

    ∀ x , y ∈ S , ρ ( x , y ) ≥ 0 且当 ρ ( x , y ) = 0 当且仅当 ξ k = η k ( k = 1 , 2 , . . . ) \forall x,y \in S,\rho(x,y) \geq 0 且当\rho(x,y)=0当且仅当\xi_k=\eta_k(k=1,2,...) x,yS,ρ(x,y)0且当ρ(x,y)=0当且仅当ξk=ηk(k=1,2,...),即 x = y x=y x=y S S S满足正定性
    ∀ x , y ∈ S , ∣ ξ k − η k ∣ = ∣ η k − ξ k ∣ \forall x,y \in S,|\xi_k-\eta_k|=|\eta_k-\xi_k| x,yS,ξkηk=ηkξk,即: ρ ( x , y ) = ρ ( y , x ) \rho(x,y)=\rho(y,x) ρ(x,y)=ρ(y,x),S满足对称性
    ∀ x , y , z ∈ S , ρ ( x , z ) = ∑ k = 1 ∞ 1 2 k ∣ ξ k − Z k ∣ 1 + ∣ ξ k − Z k ∣ = ∑ k = 1 ∞ 1 2 k ∣ ξ k − η k + η k − Z k ∣ 1 + ∣ ξ k − η k + η k − Z k ∣ ≤ ∑ k = 1 ∞ ∣ ξ k − η k ∣ 1 + ∣ ξ k − η k ∣ + ∑ k = 1 ∞ 1 2 k ∣ η k − Z k ∣ 1 + ∣ η k − Z k ∣ = ρ ( x , y ) + ρ ( y , z ) \forall x,y,z \in S,\rho(x,z)=\sum_{k=1}^{\infty} \frac{1}{2^k} \frac{|\xi_k-Z_k|}{1+|\xi_k-Z_k|}=\sum_{k=1}^{\infty} \frac{1}{2^k} \frac{|\xi_k-\eta_k+\eta_k-Z_k|}{1+|\xi_k-\eta_k+\eta_k-Z_k|} \\ \leq \sum_{k=1}^{\infty} \frac{|\xi_k-\eta_k|}{1+|\xi_k-\eta_k|} + \sum_{k=1}^{\infty} \frac{1}{2^k} \frac{|\eta_k-Z_k|}{1+|\eta_k-Z_k|} = \rho(x,y)+\rho(y,z) x,y,zS,ρ(x,z)=k=12k11+ξkZkξkZk=k=12k11+ξkηk+ηkZkξkηk+ηkZkk=11+ξkηkξkηk+k=12k11+ηkZkηkZk=ρ(x,y)+ρ(y,z)
    即有: S S S满足三角不等式

    第二步,证明 S S S是完备的:(所有的基本列都是收敛列)

    x k = ( ξ 1 k , ξ 2 k , . . . , ξ n k , . . . ) x^k=(\xi_1^k,\xi_2^k,...,\xi_n^k,...) xk=(ξ1k,ξ2k,...,ξnk,...),若 ρ ( x k , x l ) → 0 ( k , l → ∞ ) \rho(x^k,x^l) \rightarrow 0(k,l \rightarrow \infty) ρ(xk,xl)0(k,l),则:
    1 2 i ∣ ξ i k − ξ i l ∣ 1 + ∣ ξ i k − ξ i l ∣ ≤ ∑ i = 1 ∞ 1 2 i ∣ ξ i k − ξ i l ∣ 1 + ∣ ξ i k − ξ i l ∣ → 0 \frac{1}{2^i} \frac{|\xi_i^k-\xi_i^l|}{1+|\xi_i^k-\xi_i^l|} \leq \sum_{i=1}^{\infty} \frac{1}{2^i} \frac{|\xi_i^k-\xi_i^l|}{1+|\xi_i^k-\xi_i^l|} \rightarrow 0 2i11+ξikξilξikξili=12i11+ξikξilξikξil0
    { ξ i k } \{\xi_i^k\} {ξik}是Cauchy列( ∀ i ∈ N \forall i \in N iN
    于是 ∃ ξ i , s . t . ∣ ξ i k − ξ i ∣ → 0 ( k → ∞ ) \exists \xi_i,s.t. |\xi_i^k-\xi_i| \rightarrow 0(k \rightarrow \infty) ξi,s.t.∣ξikξi0(k)
    x = ( ξ 1 , ξ 2 , . . . , ξ n , . . . ) x=(\xi_1,\xi_2,...,\xi_n,...) x=(ξ1,ξ2,...,ξn,...),则有:
    ρ ( x k , x ) = ∑ i = 1 ∞ 1 2 i ∣ ξ i k − ξ i ∣ 1 + ∣ ξ i k − ξ i ∣ = ∑ i = 1 n 0 1 2 i ∣ ξ i k − ξ i ∣ 1 + ∣ ξ i k − ξ i ∣ + ∑ i = n 0 + 1 ∞ 1 2 i ∣ ξ i k − ξ i ∣ 1 + ∣ ξ i k − ξ i ∣ < ε 2 + 1 2 n 0 < ε 2 + ε 2 = ε \rho(x^k,x)=\sum_{i=1}^{\infty} \frac{1}{2^i} \frac{|\xi_i^k-\xi_i|}{1+|\xi_i^k-\xi_i|} \\ =\sum_{i=1}^{n_0} \frac{1}{2^i} \frac{|\xi_i^k-\xi_i|}{1+|\xi_i^k-\xi_i|} + \sum_{i=n_0+1}^{\infty}\frac{1}{2^i} \frac{|\xi_i^k-\xi_i|}{1+|\xi_i^k-\xi_i|} \\ < \frac{\varepsilon}{2} + \frac{1}{2^{n_0}} < \frac{\varepsilon}{2} + \frac{\varepsilon}{2} = \varepsilon ρ(xk,x)=i=12i11+ξikξiξikξi=i=1n02i11+ξikξiξikξi+i=n0+12i11+ξikξiξikξi<2ε+2n01<2ε+2ε=ε
    其中, ∀ ε > 0 \forall \varepsilon >0 ε>0,取 n 0 n_0 n0,使得 1 2 n 0 < ε 2 \frac{1}{2^{n_0}} < \frac{\varepsilon}{2} 2n01<2ε,取 N N N,当 k > N k > N k>N时, ∣ ξ i k − ξ i ∣ < ε 2 ( i = 1 , 2 , . . . , n 0 ) |\xi_i^k-\xi_i|<\frac{\varepsilon}{2}(i=1,2,...,n_0) ξikξi<2ε(i=1,2,...,n0)
    即: S S S所有基本列为收敛列

    展开全文
  • 数学的进步是集合完备化与映射简洁化的共同作用 。映射的简化会催化新的定义的产生,新的定义往往又会衍生出新的完备化过程,两者此消彼长,可看成是一个过程的两个对偶的方面。这篇文章会试着来讲述这个完备化过程...

    本质上讲,技术只能处理线性问题,非线性属于佛陀。

    前言

    数学是基于公设的,数学的进步是集合完备化与映射简洁化的共同作用 。映射的简化会催化新的定义的产生,新的定义往往又会衍生出新的完备化过程,两者此消彼长,可看成是一个过程的两个对偶的方面。
    这篇文章会试着来讲述这个完备化过程,进而讲述完备化后的空间中的线性算子。简单的说完备化就是把某个函数的值域扩充进已有集合的过程。从实用的角度来看,完备化的目的是为了更好的研究线性算子(所有的对非线性算子的研究其实都是研究其如何以更加简洁的形式转化为线性)。本文首先从数的构造说起。

    实数的构造

    实分析用到的各种数系,按照复杂性递增的次序,它们是自然数系 N \mathbb{N} N、整数系 Z \mathbb{Z} Z、有理数系 Q \mathbb{Q} Q以及实数系 Z \mathbb{Z} Z。自然数系 { 0 , 1 , 2 , 3 , ⋯ &ThinSpace; } \left \{ 0,1,2,3,\cdots \right \} {0,1,2,3,}是最原始的数系,它的一个标准定义是由皮亚诺公理给出的。从自然数到整数是对减法映射的值域做并的结果,从加法群的角度上,这是的一个完备化过程。整数加群作为核心元素,活跃在数学的所有分支。
    有理数是整数对除法映射做并的结果,当然,我们必须遵从通常的禁率,分母不得为0。因为如果允许 b b b为0的话,将不能保持两个恒等式 ( a b ) × b = a \left ( \frac{a}{b} \right )\times b=a (ba)×b=a c × 0 = 0 c\times 0=0 c×0=0同时成立,域的结构就会遭到破坏,也就失去了完备化的意义。对于有理数这个名称的由来,是翻译的rational,其实这里是数学家前辈犯的一个美丽的错误,ratio是比例的意思,nal是后缀,而不能翻译成通常的“合理的,理性的”。这样的错误以讹传讹,叫的人多了而且由于其的朗朗上口最终就索性这样传下来了。有些很个性的学者愣是在自己的著作里使用的是“比例数”而非“有理数”。
    公元前500年,古希腊毕达哥拉斯学派的弟子希帕索斯发现了一个正方形的对角线与其一边的长度的比值不是有理数。这一发现使该学派领导人惶恐、恼怒,认为这颠覆了他们的信仰。希帕索斯因此遭到了沉舟身亡的惩处。
    但希帕索斯的发现和思考,第一次揭示出了有理数系的缺陷,证明有理数并没有填满数轴,在数轴上还存在着大量的“孔隙”,推动数学学科向前迈进了一大步。

    柯西数列构造实数

    柯西数列是微积分存在的基础,它很好的定义了豪斯多夫空间的收敛的概念。为了研究微积分学,就必须构造对柯西数列完备的数系和空间,简称为数列完备。实数是柯西数列完备化有理数的结果,也可看成是柯西数列的完备集。一个有理数列可看成是一个从自然数到有理数的映射,它把每一个大于等于 m m m的序数 n n n映射到数列的一个有理数元素 a n a_{n} an。当一个有理数列,对于每个有理数 ε \varepsilon ε,存在 N ⩾ 0 N\geqslant 0 N0,使得对一切 j , k ⩾ N j,k\geqslant N j,kN,满足 d ( a j , a k ) ⩽ ε d(a_{j},a_{k})\leqslant \varepsilon d(aj,ak)ε,则这个有理数列构成柯西数列。
    很容易证明的是,每个柯西数列都是有界的,则所有的柯西数列的极限的集合构成实数。也可以说成柯西数列的全体构成实数域也是对的。为了保证我们的实数集合整洁(否则一个元素会出现多次),需增加限制条件,构作等价类。进一步可以证明,限制离开零(所有的元素非零)的柯西数列关于等价类构成的集合对于加、减、乘、除四个映射是封闭的。则说明构成域,即为实数域。

    复数域

    实数域的发现为微积分提供了完美的舞台,但实数并非最大的数域,在实数的基础上对 i = − 1 i=\sqrt{-1} i=1 完备化得到了复数域,是目前所知的最大的数域。数学家哈密顿构造了我们工程上经常用到的四元数集合,它有三个虚部,可看成是复数的扩展,但它不是域,只是个除环,比域少了交换律。所以说,复数是“数”,而quaternion翻译成四元数更多的是向复数看齐,其本身并不是“数”。
    复数域的发现极大的丰富了数学的表达、计算能力,比如幂级数有着非常简单的结构和非常强大的表现力,是最简单的解析函数项级数,但在实数域是无法真正的看清楚的,直观的解释是在实数域要找一个无穷可微的函数是非常苛刻的。而在实数域可导的函数就可以很容易的扩展为复数域的解析函数,在复数域,解析函数是具有无穷可微性的,也就可以很容易的展开为幂级数,并且可进一步扩展为更为广义的洛朗级数。在幂级数理论中处于核心地位的泰勒定理是这样描述的:设 f ( z ) f(z) f(z)在区域 D D D内解析, a ∈ D a\in D aD,只要圆 K K K ∣ z − a ∣ &lt; R \left | z-a \right |&lt;R za<R含于 D D D,则 f ( z ) f(z) f(z) K K K内能展成幂级数。而且它的逆命题也是成立的:任意一个具有非零收敛半径的幂级数在其收敛圆内收敛于一个解析函数。Z变换就是在这样的性质的基础上产生的,是针对函数离散的情况。
    再比如,在实数域很难积分的情况,在复数域可能就会比较容易的得到解决,因为在复数域两点之间的有向路径很多,并不像实数域只有一条。复变函数单值解析分支上的任何积分路径都是等价的。

    线性空间

    大部分的数学理论都是必须在线性空间中才能发挥作用的。一个复杂的拓扑空间,首先要想方设法的把它转化为流形,然后或者在局部构作欧式空间(见下图,图片摘自老顾谈几何),或者在流形上寻找群结构进而构作李代数,最后在构作的线性空间上进行相应的分析。线性空间也叫向量空间。
    流形的定义
    为了在线性空间中表达距离,引入了范数。为了在线性空间中同时表达角度和距离,引入了内积。引入这些映射是为了线性空间的度量,统称为度量空间。度量空间的完备化靠的也是前面讲述的柯西数列,最为常见的度量空间为欧几里得空间,傅里叶级数、黎曼积分、线性代数及欧式几何都是基于它发展起来的,在我们计算机算法中,都是在欧式空间上才能进行算法设计,数学技巧主要体现在如何把复杂的空间结构转化为欧式空间 。但对于绝大多数的计算机专业的科技人员,能掌握欧式空间的理论也已经足够了。
    矩阵是一个数学模型,是对欧式空间上的线性变换的抽象,工科课程线性代数围绕着矩阵讲个不停,实际上就是在讲欧几里得空间的线性变换,这是基于如下的一个重要的定理:设 V V V V ′ {V}&#x27; V分别是域 F F F n n n维、 s s s维线性空间,则 V V V V ′ {V}&#x27; V的线性映射 A A A与它在 V V V的一个基和 V ′ {V}&#x27; V的一个基下的矩阵 A A A的对应是线性空间 H o m ( V , V ′ ) Hom(V,{V}&#x27;) Hom(V,V) M s × n ( F ) M_{s\times n}(F) Ms×n(F)的一个同构映射,从而 H o m ( V , V ′ ) ≅ M s × n ( F ) Hom(V,{V}&#x27;)\cong M_{s\times n}(F) Hom(V,V)Ms×n(F)并且 d i m ( H o m ( V , V ′ ) ) = s × n = d i m ( V ) × d i m ( V ′ ) dim(Hom(V,{V}&#x27;))=s\times n=dim(V)\times dim({V}&#x27;) dim(Hom(V,V))=s×n=dim(V)×dim(V)
    在这里同构不仅仅是矩阵空间与线性映射空间的同构,它们上面的运算也是同构关系,所以可以构造矩阵范畴与线性映射范畴之间的同构态射,即是范畴之间的同构关系。在一定程度上欧几里得空间已经足够完备,所有与应用直接相关的技术问题都是基于欧几里得空间。但是,以狄拉克函数为代表的广义函数又引发了数学家的思考革命。

    狄拉克函数

    本世纪初,工程师Heaviside在解电路方程时,需要对如下函数求导函数 δ ( x ) \delta (x) δ(x) Y ( x ) = { 1 ( x ⩾ 0 ) 0 ( x &lt; 0 ) Y(x)=\left\{\begin{matrix} 1 &amp; (x\geqslant 0)\\ 0&amp; (x&lt; 0) \end{matrix}\right. Y(x)={10(x0)(x<0)但是在欧几里得空间上该函数并不可微,因此 δ ( x ) \delta (x) δ(x)不可能是函数,它除了作为一个记号,在数学上本来是没有意义的。可是,这个 δ ( x ) \delta (x) δ(x)在实际中却是非常重要的,它代表了一种理想化了的“瞬间”单位脉冲。所谓单位是指:积分为1。所谓瞬时,是指发生的时间区间趋于0。这在通信行业上也叫做冲激信号,描述冲激信号的就是狄拉克函数 。可在欧几里得空间中,它并不能作为一个函数去解释,这说明了欧几里得空间还不够完备,需要扩展。
    学者们不久就发现了狄拉克函数的自变量是什么样的: δ ( φ ) = φ ( 0 ) ( φ ∈ f u n c t i o n S p a c e ) \delta (\varphi )=\varphi (0)\left ( \varphi \in functionSpace \right ) δ(φ)=φ(0)(φfunctionSpace) 可以看到,狄拉克函数的自变量是个函数(属于基本空间 D ( Ω ) D(\Omega ) D(Ω)),可否用这些函数来扩充欧几里得空间?使其完备化?这就诱导产生了希尔伯特空间。

    希尔伯特空间

    希尔伯特空间就是完备的内积空间,它可以是不可数维数的,也可以是可数维数的,也可以是有限维数的(欧几里得空间)。它是为了定义泛函而完备化欧几里得空间的结果。泛函,通俗的讲,它包括了传统的函数和“函数的函数”(广义函数是线性连续的,可看成是泛函的子集)。也可以简单的理解为:希尔伯特空间是把若干像狄拉克函数这样的函数包容进欧几里得空间的结果,使得得到的空间能够对狄拉克这类的函数完备。
    希尔伯特空间的发现使得数学学科爆炸式增长,为了适应不同的分支,产生了很多不可数维希尔伯特空间的稠密子空间(还是希尔伯特空间),比如为了研究偏微分方程,需要刻画针对任意阶导数的收敛性,需要重新定义范数来刻画这种收敛性,这就产生了索伯列夫空间。对应于欧几里得空间中变换可逆的思想,人们发现,每个正定对称函数 K ( t , s ) K(t,s) K(t,s)都一一对应一个至多可数维的希尔伯特空间,并且非常容易的构造基底,即为再生核希尔伯特空间。这个正定对称函数 K ( t , s ) K(t,s) K(t,s)称为核函数,同时,所有的核函数也构成一个空间,通过它,复杂的希尔伯特空间得到了极大的简化。
    正交变换是性质很好的一类变换,“好”首先体现在简洁,它直接对应的是正交基,可以把复杂的空间分解为若干简单的空间的直和形式。以及对乘法封闭,构成群,而且维数低;同时是个保角变换、保距变换;另外 正交变换有着非常明确的物理意义——即表示饶任意轴的旋转,当然也可以很容易的反演。标准正交基下的数学模型往往非常简单,在计算机软硬件中更容易的实现。可是,不同于欧几里得空间,希尔伯特空间的基的构造并不容易,寻找既简单又正交而且“性能优越”的基底更是可遇不可求的事情。
    1807年,法国数学家Fourier向法国科学院递交了一份报告,在报告中他指出,任何周期函数都可以近似表示为不同频率的正弦波和余弦波的叠加: f ( t ) ≈ a 0 2 + ∑ n = 1 ∞ ( a n c o s n ω t + b n s i n n ω t ) f(t)\approx \frac{a_{0}}{2}+\sum_{n=1}^{\infty }\left (a_{n}\mathit{cos}n\omega t+b_{n}\mathit{sin}n\omega t\right) f(t)2a0+n=1(ancosnωt+bnsinnωt)
    更为重要的是下式的成立: ∫ − π π c o s m x ⋅ c o s n x d x = ∫ − π π s i n m x ⋅ s i n n x d = π δ m , n \int_{-\pi }^{\pi}cosmx\cdot cosnxdx=\int_{-\pi }^{\pi}sinmx\cdot sinnxd=\pi\delta _{m,n} ππcosmxcosnxdx=ππsinmxsinnxd=πδm,n 其中 δ m , n = { 1 m = n 0 m ≠ n \delta _{m,n}=\left\{\begin{matrix} 1 &amp; m=n\\ 0 &amp; m\neq n \end{matrix}\right. δm,n={10m=nm̸=n如上事实就表明不同频率的三角函数构成正交基。然而,该正交基是可列维的(离散的),把它扩充为不可列维(连续)空间的正交基一是为了完备化,二是为了能更加充分的而不仅仅是近似表达 L 2 L_{2} L2空间的函数。把上面的傅里叶级数形式细化为积分形式: f ( t ) = ∫ 0 ∞ [ u ( ω ) c o s ω t + v ( ω ) s i n ω t ] d ω f(t)=\int_{0}^{\infty }\left [ u(\omega )cos\omega t+v(\omega )sin\omega t \right ]d\omega f(t)=0[u(ω)cosωt+v(ω)sinωt]dω 这里,其实正弦函数和余弦函数是没有本质区别的,都是波函数,只不过相位不同而已,而他们的系数又是不同的函数,格式上的冗余在数学领域是不能容忍的。作为最令人着迷的公式——欧拉公式: e π i + 1 = 0 e^{\pi i}+1=0 eπi+1=0,可推导得到更一般的: e i x = c o s ( x ) + i s i n ( x ) e^{ix}=cos(x)+isin(x) eix=cos(x)+isin(x)表明,如函数 f f f可以用指数级数线性表出,那么 f f f也可以写成实数域傅里叶级数形式。指数级数形式在很多文献中也称为复数域的傅里叶级数。设 e k ( x ) = e 2 π i k x e_{k}(x)=e^{2\pi ikx} ek(x)=e2πikx,则 ⟨ e k , e l ⟩ = { 1 , i f k = l 0 , i f k ≠ l \left \langle e_{k},e_{l} \right \rangle=\left\{\begin{matrix} 1, &amp; if k=l\\ 0,&amp; if k\neq l \end{matrix}\right. ek,el={1,0,ifk=lifk̸=l可知周期或连续指数映射构成一个希尔伯特空间的标准正交基,而且形式上比实数域的三角函数还要简洁!这样函数 f f f就可表示为 f ( x ) ≈ ∑ k ∈ Z c k e 2 π i k x f(x)\approx\sum_{k\in \mathbb{Z}}^{ } c_{k}e^{2\pi ikx} f(x)kZcke2πikx对每个 k k k c k = ⟨ f , e k ⟩ c_{k}=\left \langle f,e_{k} \right \rangle ck=f,ek。可这毕竟是离散化的模型,是个近似表达,如果想得到更为严格的恒等式,需要对上面的和式无限细分,并以原点对称展开,即求得其黎曼积分形式,如下 f ( t ) = ∫ − ∞ ∞ f ^ ( ω ) e 2 π i ω t d ω f(t)=\int_{-\infty }^{\infty }\hat{f}(\omega)e^{2\pi i\omega t}d\omega f(t)=f^(ω)e2πiωtdω此即为傅里叶逆变换形式。 f ^ ( ω ) \hat{f}(\omega) f^(ω)是傅里叶变换,它可看成是不可数维希尔伯特空间上的正交变换 ( ℑ f ) ( ω ) = f ^ ( ω ) = ∫ − ∞ ∞ f ( t ) e − 2 π i ε ω t d t \left ( \Im f \right )(\omega)=\hat{f}(\omega)=\int_{-\infty }^{\infty }f(t)e^{-2\pi i\varepsilon \omega t}dt (f)(ω)=f^(ω)=f(t)e2πiεωtdt傅里叶变换,不但基底和表达式非常简单,是不可数维希尔伯特空间的正交变换(数学上的完美性),而且具有非常明晰的物理含义(表达上的直观性)。快速算法的发明使得它非常广泛的应用于光学、数字信号处理、数值模拟等领域(计算上的有效性)。在数学领域这是不多见的,是基础学术与工程的真正的完美结合。离散傅里叶变换的快速算法,看似简单,却需要深入理解傅里叶,挖掘到 e − i 2 π / N e^{-i2\pi /N} ei2π/N的对称性和周期性,我想,所有的算法工程师都是梦寐以求能设计出这样的算法的。
    但是,傅里叶变换对诱因稳定的,具有周期特性的信号往往有着非常好的频域特征提取能力,但不可能对所有的这样的需求都是效果好的(尤其是一些有着突变的局部特征的需求),有些特例在频域分析的时候就需要用特殊的基底,否则一些局部的重要特征就很难在频域得到很好的呈现,这推动着科学家和工程师向前探索,直到小波的发现。
    小波最先在工程中应用是分析人造地震数据。事实上,人耳在初次识别声音时就已经使用了小波变换。振动波从耳鼓传到耳膜在整个耳蜗中延伸,其过程是以螺旋方式进入耳内的。假设其包络函数: ϕ ( x ) \phi (x) ϕ(x),可推出(推导过程不在这里给出了,小波十讲对此有简单的表述): ψ ^ ( e − x ) = ( 2 π ) − 1 / 2 ϕ ( x ) \hat{\psi}(e^{-x})=(2\pi)^{-1/2}\phi (x) ψ^(ex)=(2π)1/2ϕ(x)经整理可得该过程的小波基的表达式。
    但是,这里的包络函数: ϕ ( x ) \phi (x) ϕ(x)很难简化到我们容易仿真的程度,大自然的复杂度是无限的,我们人类的认知能力永远只能逼近它的一小部分。所以说小波基的构造这样一个看似是应用的问题,可是实际上确是属于纯数学的课题。
    在这里插入图片描述
    至今学术界设计小波尺度函数时考虑的仅仅是光滑度、复杂度、支集以及衰减速度(是否可用速降函数空间中的函数进行逼近)等,远没有能针对速降函数空间的某稠密子集来一一构造合适的特殊的正交小波基的能力。傅里叶变换在构造小波尺度函数的算法中依然起到了核心作用,很多年前看到过一句话:傅里叶变换是当代分析学的核心,恐怕不为过。
    本人是一名热爱科学的工程师,在傅里叶中看到“美”的真正内涵,也看到了它在工程上的四两拨千斤。这样的感觉,在本人所经历的目前还是为数不多,本人这些年致力于寻找的工程与学术的美的结合,傅里叶之外,还在哪里呢?

    展开全文
  • 图灵机与图灵完备

    2021-12-02 19:22:02
    RNN已被证明是图灵完备的,因此,RNN可以解决任何可计算问题 基于Brainfuck感受图灵完备 当下的主流编程语言(C++,Java,Python)都是图灵完备的语言。回到语言的底层,一切编程语言实现的功能完全一样,本质上...

    图灵机Turing Machine

    图灵机来自图灵1936年的文章"On Computable Numbers, with an Application to the Entscheidungsproblem"(论可计算数及其在判定性问题上的应用)中提出的思想,论文指出,只要图灵机可以被实现,就可以用于解决任何可计算问题

    图灵机的结构为:

    • 一条无限长的纸袋(tape),纸带被分成一个个相邻的格子(square),每个格子都可以写上至多一个字符(symbol);
    • 一个字符表(alphabet),即字符的集合,它包含纸带上可能出现的所有字符(包括特殊的空白字符);
    • 一个读写头(head),可理解为指向其中的一个格子的指针。它可以读取,擦除,写入当前格子的内容,此外也可以每次向左或右移动一个格子;
    • 一个状态寄存器(state register),它追踪着每一步运算过程中,整个机器所处的状态(运行或终止)。当这个状态从运行变成终止,则运算结束,机器停机并交回控制权。
    • 一个有限的指令集(instructions table),它记录着读写头在不同情况下应该执行的行为。可以想象为读写头对应的操作指南。比如"当前处于编号53的格子,看到其中内容为0,则擦除,改写为1,并向右移动一格,下一状态为运行"。指令集就对应着计算模型,即函数

    在计算开始前,纸带可以是完全空白的,也可以预先写入字符。运算开始时,读写头从某一位置开始,严格按照此刻的配置(configuration),即:

    • 当前所处位置;
    • 当前格子内容;

    一步步对照着指令集去进行操作,直到状态变成停止,运算结束。而纸带留下的字符序列作为输出,由人为解码为自然语言。

    可计算问题

    图灵在图灵机思想中证明了,假设上述所说的功能都能以某种物理形式实现,那么任何可计算问题都可以被解决。

    在计算机领域,我们研究的一切问题都是计算问题,计算问题泛指一切与计算相关的问题。比如:

    • 给定一个正整数 n n n,判断它是否是质数;
    • 给定一个0-1序列,把它们按位取反;
    • 给定一个字符串,判断某个字符是否存在,以及查找存在的位置;
    • 给定一个蕴含逻辑的命题,求它的逆否命题;

    相反,非计算问题为:

    • 今晚看什么书;
    • 你为什么叫白景屹;

    计算问题有的可解决,有的不可解决。从而引出计算问题的可计算性(computability),它可以被理解为"是否存在一个算法,能解决在任何输入下的此计算问题"。比如上面的问题"给定一个正整数,判断它是否是质数"。我们确实可以找到一个算法判断一个数是不是质数,比如从2遍历到 n − 1 n-1 n1,看 n n n是否可以整除它,因此,这个问题是可计算的。

    对于不可计算的计算问题,比如停机问题(Halting Problem):给定一段程序的描述和该程序的一个有效输入,运行这个程序,程序最终是会终止还是陷入无限循环。

    很明显,这个计算问题不可计算,我们不能找到一个算法在任何情况下都判断它。

    回到可计算问题,换言之,对于一个问题,对于任意输入,只要人类可以保证算出结果(不管花费多久),则图灵机也可以保证算出结果(不管花费多久)。

    图灵完备Turing Completeness

    图灵完备性是针对一套数据操作规则而言的概念。数据操作规则可以是一个编程语言,也可以是计算机里具体的一个指令集。当这套规则可以实现图灵机模型里的全部功能时,就称它具有图灵完备性。

    也就是当一套数据操作具有图灵完备性时,该数据操作可以解决任何可计算问题。


    RNN已被证明是图灵完备的,因此,RNN可以解决任何可计算问题


    基于Brainfuck感受图灵完备

    当下的主流编程语言(C++,Java,Python)都是图灵完备的语言。回到语言的底层,一切编程语言实现的功能完全一样,本质上就是一个图灵机。

    Brainfuck(BF),是一种极小化的程序语言,它是由Urban Müller在1993年创造的。它一共只包含8个有效字符,每个有效字符就是一条指令。语言非常接近机器指令,比如:

    ++++++++++[>+++++++>++++++++++>+++<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.
    

    编译后,控制台打印"Hello World!"。BF的工作机制与图灵机高度一致。首先存储数据的方式是一个不限长的一维整数数组,里面的数值全部初始化为0。此外,还有一个数据指针,每一时刻都指向数组的某一任意元素。指针可以向左或向右移动,也可以读取或修改当前值。

    BF中的8个有效字符为:

    字符含义
    >指针向右移动1格
    <指针向左移动1格
    +使指针当前格中的数值加1
    -使指针当前格中的数值减1
    .把当前格中的数值按ASCII表输出到终端
    ,从终端接受1byte数据,存储其ASCII对应的数值到当前格
    [当指针当前值为0时,程序跳转至与之对应的 ] 之后;否则程序正常执行
    ]程序跳转回与之对应的 [ 处
    展开全文
  • 图灵完备

    2021-02-26 16:59:09
    一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的。一个能计算出每个图灵可计算函数(Turing-computable function)的计算系统被称为图灵完备的。一个语言是图灵完备的,意味着该语言的计算能力与一...
  • 图灵完备是什么意思

    2022-04-28 15:38:05
    一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的。 一个能计算出每个图灵可计算函数(Turing-computable function)的计算系统被称为图灵完备的。一个语言是图灵完备的,意味着该语言的计算能力...
  • 图灵完备
  • “非图灵完备”到底意味着什么

    千次阅读 2020-04-30 02:34:43
    设计一个图灵非完备的编程语言 。这件事情在外行人看来一点也不酷。就好比如果有人声称自己要做个“解决宇宙间一切计算问题的终极语言”,不管做得出来做不出来,总会有人把他奉若神明;也许很少有人意识到,只要有...
  • 图灵完备 状态机

    2021-04-08 15:35:36
    一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的。 图灵完备是什么意思呢? 在可计算理论中,当一组数据操作的规则(一组指令集,编程语言,或者元胞自动机)满足任意数据按照一定的顺序可以...
  • 什么是图灵完备性(Turing complete)?

    万次阅读 多人点赞 2020-10-18 20:09:25
    作者:Ran C ...来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。... 直观理解图灵完备——Brainfuck语言 1. 什么是图灵机 图灵机(Turing Machine)是图灵在1936年发表的 "On .
  • 图灵完备是什么?

    2021-02-26 16:59:13
    简单来讲,一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的.当然图灵完备也可以因为陷入死循环而导致程序崩溃.在某些场景中图灵完备需要限制语言,有循环执行语句,判断分支语句等.举个例子,...
  • 确界原理证明实数完备性定理

    千次阅读 2020-07-21 11:53:09
    确界原理证明其他实数完备性基本定理 确界原理:非空有界上(下)数集,必有上(下)确界 1.确界原理证明单调有界定理 单调有界定理:任何单调有界数列必有极限 证:不妨设 {an}\{ an \}{an}为有上界的递增数列. ...
  • 图灵完备 – 维基百科 在可计算性理论里,如果一系列操作数据的规则(如指令集、编程语言、细胞自动机)可以用来模拟任何图灵机,那么它是图灵完备的。这意味着这个系统也可以识别其他数据处理规则集,图灵完备性被...
  • 图灵完备-概念理解

    2020-04-27 13:22:32
    一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的。 一个能计算出每个图灵可计算函数(Turing-computable function)的计算系统被称为图灵完备的。 一个语言是图灵完备的,意味着该语言的计算...
  • 一切可计算的问题都能计算,这样的虚拟机或编程语言就叫做图灵完备的。一个能计算处每一个图灵可计算函数的计算系统被称为图灵完备的。 一个语言是图灵完备的,意味着该语言的计算能力与一个通用图灵机相当,这也是...
  • 证明:设{}是中的柯西点列,其中={} 由柯西列的定义:对,正整数N,当n,m>N时, 因此,对每一个固定的j,当n,m > N时,成立 ... 这就是说,数列是柯西点列(注意此处是指是R中的Cauchy列),...由R的完备...
  • “哥德尔不完备定理”是针对公理体系的一项结论,它之所以如此伟大且深刻,正是因为它撼动的是一切科学的研究基础——公理体系。 修炼第一重神功的时候,我们简要理解“哥德尔不完备定理”说的是: 一个足够复杂的...
  • 来源:人机与认知实验室(一)【中文网上深入介绍哥德尔不完备定理的文章很少,我这篇文章写得很长,花了不少时间打磨它,希望能帮助到爱好数学与逻辑的人。文章把理解哥德尔不完备定...
  • 命题逻辑的soundness可靠性和completeness完备

    千次阅读 多人点赞 2017-11-08 23:14:49
    命题逻辑中的语法与语义,可靠性与完备性1 导言 初学数理逻辑的时候,一个非常重要的点就是对可靠性与完备性概念的理解,这两个概念极为重要,却又经常让人觉得 难以理解。 说它重要是因为它涉及逻辑系统的基本框架...
  • 关注:决策智能与机器学习,聚焦AI干货编者按:智能技术要在理论研究方面必须要解决非线性现象的可建模机理与规律,其中哥德尔不完备定理不容忽视,哥德尔不完备定理、塔尔斯基形式语言真理论,图灵...
  • 图灵完备是什么?

    千次阅读 2020-01-10 21:03:43
    简单来讲,一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的。当然图灵完备也可能因为陷入死循环而导致程序崩溃。 在某些场景中图灵完备需要限制语言,有循环执行语句,判...
  • 一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的。  一个能计算出每个图灵可计算函数(Turing-computable function)的计算系统被称为图灵完备的。一个语言是图灵完备的,意味着该语言的计算...
  • 本书的特色是通过一些精心设计的有趣而又颇具指导意义的程序,对实用程序设计技巧及基本设计原则进行了透彻而睿智的描述,为复杂的编程问题提供了清晰而完备的解决思路。本书对各个层次的程序员都具有很高的阅读价值
  • 图灵完备

    千次阅读 2018-08-03 21:27:51
    这个词源于引入图灵机概念的数学家艾伦·图灵(Alan Turing)。 图灵机会受到存储能力的物理限制。 图灵完备通常指具有无限存储...简单来说,一切可计算的问题都能计算,这样的虚拟机或者编程语言就叫图灵完备的。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,706
精华内容 7,882
热门标签
关键字:

一切完备