V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
James369
V2EX  ›  程序员

看到另外一种“图灵完备”的解释

  •  
  •   James369 · 2022-06-15 08:10:28 +08:00 · 3059 次点击
    这是一个创建于 652 天前的主题,其中的信息可能已经有所发展或是发生改变。

    在看 AI 的时候看到的:所有的图灵机都可以被一个由使用 Sigmoid 型激活函数的神经元构成的全连接循环网络来进行模拟。

    完全看不懂什么意思?

    第 1 条附言  ·  2022-06-15 22:02:34 +08:00
    这是出自邱教授的《神经网络与深度学习》 ,好多数学公式看得眼花缭乱,真佩服这些搞学术的
    6 条回复    2022-06-15 13:46:26 +08:00
    phpfpm
        1
    phpfpm  
       2022-06-15 09:33:59 +08:00
    1 你确定你知道什么是图灵机?
    2 你确定你知道什么是激活函数,以及 sigmoid 是什么?
    3 你确定你知道全连接循环网络是什么?

    知道以上三个,连在一起为啥不懂呢
    liuser666
        2
    liuser666  
       2022-06-15 09:36:53 +08:00   ❤️ 1
    本质上是因为 sigmoid 型激活函数的神经网络可以模拟任何函数。
    czfy
        3
    czfy  
       2022-06-15 09:57:49 +08:00
    Sigmoid 型激活函数
    激活函数:节点对输入处理的规则,最简单的处理规则是 f(x)=kx+b ,神经网络里的激活函数通常是非线性的
    Sigmoid 函数:有界、可微的实函数,在实数范围内均有取值,且导数恒为非负,有且只有一个拐点。在神经网络里,S 型函数通常特指 Logistic 函数

    神经元:节点

    全连接循环网络
    全连接网络:第 n-1 层的任意节点,都和第 n 层的所有节点有连接
    循环网络:Recurrent neural network ,RNN ,循环神经网络

    基于这些 google 出来的信息,这句话的意思我推测大概是:
    包含上面这些元素的人工神经网络,可以对图灵完备的某个东西进行模拟
    lyminghao
        4
    lyminghao  
       2022-06-15 12:33:29 +08:00
    这个没毛病啊
    geelaw
        5
    geelaw  
       2022-06-15 12:52:32 +08:00 via iPhone   ❤️ 1
    单从这句话确实看不懂,至少我并不知道 RNN 和它“所计算的函数”是如何定义的(有很多细节会影响结论是否成立、结论是否令人意外)。

    看这篇应该就明白了 https://www.sciencedirect.com/science/article/pii/089396599190080F

    另外,这并不是 Turing 完备的“解释”,这句话是在利用 Turing 完备的词义,而不是在告诉你 Turing 完备的词义。(类比:这家火锅很辣,这句话没有在解释什么是“辣”,而是在利用“辣”的意思给那家火锅下判断。)
    ipwx
        6
    ipwx  
       2022-06-15 13:46:26 +08:00
    这种结论一般都是构造法证明。

    首先图灵机是什么有清晰的定义。然后就是怎么用 sigmoid + rnn 表达任意给定的图灵机了。

    随便搜一下可得:

    Turing Completeness of Bounded-Precision Recurrent Neural Networks
    https://openreview.net/forum?id=IWJ9jvXAoVQ

    这篇 2021 年的 poster 说,前人的工作需要假定无穷精度的 RNN 才能表达任意图灵机。现在他们可以用有限精度 RNN 来表达了(可喜可贺
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3137 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 13:01 · PVG 21:01 · LAX 06:01 · JFK 09:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.