啊看来这种公益项目还是救命啊，可惜我网上经济不自由不能使用付费服务

最近客户端问题非常大,,,,

https://github.com/LineageOS/android_frameworks_base/blob/gingerbread-release/tools/aapt/Resource.cpp #Android #bin

#blog #recommended https://bindog.github.io/

我只能最后改正之前错误的 NP-hard 问题什么的了... 其余的，下周说、下周做吧。 🤐

时间真的不够用

0. 这是什么

本频道上上周讲事的时候，讲错了一点，必须即时修正（皮一下，玩个个人的梗）
（我是在强调我修错修的快！）（所以不要告 typo）（是即时编译的即）

虽然我这周很多事情没有做（比如重写别人的 TextTag，比如写 SimpleCat 解释器和策划 NaiveCat、还有写 BinaryStreamIO、用 GeekSpec 1.0 重写 GeekApk 服务定义... 等等十几项）
（也会导致我下周在学校里不能看新书了，我要看文学书.... 这么多都是必须写的堆在哪里...）

但是我这个人呢，一直重视改错的，我和王垠一样总是在更新自己（又皮一下，又玩个个人的梗）（终于说了句大实话）

（好啦 duangsuse 毒舌...）
（只是玩梗而已，无恶意啦）

1. 这个问题出在哪里

-> 某条历史回顾消息广播

2. 是啥类型的问题

很智障的计算机科学定义混淆

3. 你打算怎么改

👇

=> 最后一次，drakeet 提到一个数组（线性表）优先级排序的问题（OI 入门内容，所谓初等内容都是 dfs bfs 这种的，计算机可解的数学问题，游戏模拟、递归算法、关系代数，稍微搞基一点的离散化、编译原理、神经网络）
就是你们之前看到纯纯支持 Book 的 Chapter 手动排序的特性，他在群里讨论了一下，（想了一段时间）说是逻辑上冲突无法实现，我表达了一下自己的看法『你可以做 Pin Chapter 的功能啊，我觉得应该会用得到』，但是 drakeet 觉得这依然是 NP-hard 问题（他觉得这类似停机问题，是不能解决的，我的观点大概就是不必须使用优先级排序，排序什么的有很多方法，都好说，『半自动排序半手动』是完全可行的），我最后甚至用 Ruby 写了个算法实现（就是能够 Pin 数据的 Array，并且可以自动 sort，sort 完手动 pin 的数据依然在表头部），结果就被踢了.... 🙁


出错的部分在这段话里，这里提到的 Chapter 现在在纯纯写作中被称为『文章』应该，反正纯纯写作把文章集合称为『书』Book，然后文章就是你们编辑（随机插入删除）的东西，我对这些名称不负责，就是表示这些。


『drakeet 觉得这依然是 NP-hard 问题』

👉 后面和『停机问题』逻辑并列

这是错误的，因为停机问题和 NP-hard 不是一种概念

并且，停机问题也不是『不能解决』的，实际上，停机问题早就被证实了

好了这周就这么多

#School #life duangsuse 清明好！放假三天！

三天里不打算熬夜。

#CS #fix 下面我来给大家解释一下停机问题和 NP 困难到底是什么，和我这里提到的 NP-hard 和停机问题指的是什么。


== 上个消息里，我对 NP-hard 和 停机问题 的理解

NP-hard: 就是 NP 完全问题，算法上，就是指很难解决的问题，比如旅行商问题和集合覆盖问题，这类问题的最优解通常要枚举出幂(mì)集（所有可能出现的子集甚至序列），使用穷举法，他们的时间复杂度甚至可能是 O(n!) （n! 代表 factorial(n)）

这是相当恐怖的时间复杂度，这意味着只要需要处理的数据集足够大 — 并不需要太大的数据输入，程序就无法在一个合理的时间内得到解了。

故此，一般使用贪婪算法得到近似解。

也可以了解一下 Ackerman 函数，但由于我不是特别了解算法和线性代数、离散数学什么的.... 也要学啦。
啊因为提到了 Ackerman 函数，不如再提一下 Collatz 函数 Collatz 猜想

这是错误的理解（指 NP-hard = NP-complete），而且 NP-hardness 和 NP-completeness 也不是一个概念

停机问题: 一个确定性问题，当时被我当成了一个命题（误会，因为确定性问题不一定是命题...）

就是说：有没有一个程序，可以判断所有程序是否能在有限的时间内完成计算？

这应该不是一个命题（不是陈述句）

不过可以改成陈述句的形式，这涉及到自然语言处理（语言学）的内容... 欸话说大家知道啥是谓词么？谓词（predicate）在计算机科学中也是一个专业术语。

猫"是"动物

—

我(r)"爱"(v)你

(r)


主 动(谓词) 宾

汉语的谓词包括动词和形容词


欸话说，机器学习是个好东西，让程序自己根据数据来造更有意义的数据是很有趣的事情，对 NLP 来说，可是我不知道 HMM(隐马尔科夫链) 这些东西... 话说 Regex 模式匹配用的状态机 DFA, NFA 什么的也不清楚，只是刚好入门软件工程而已，电子电路和数控、CAD、PLC/PLA 什么的也不了解... 尤其是线性代数和优化问题、机器学习、DIP、3D Modeling(欸怎么跨界了？) 什么的...

https://github.com/hankcs/HanLP/

但其实呢，停机问题是（在图灵完全的模型里）判断一个程序是否能在有限时间内完成的确定性问题，并且，当然地，这个解决方案得是停机的

这是不可能解决的问题。因为如果能判断的话，就只能证明这个问题不可判断了，或者说（从某王博客上抄的，我记得他有发）

（没抄到... 忘记哪篇博文了）

The halting problem is the problem of determining, when running an arbitrary program with an input, whether the program halts (finish running) or does not halt (run forever).

也可以参考理发师悖论

因为如果有一个程序可以判断它自己是否停机，它就可以利用判断的结果进行相反的操作（比如判断是否停机，如果是，则直接无限循环，否则就真正让程序停机）

https://weblogs.asp.net/dixin/lambda-calculus-via-c-sharp-24-undecidability-of-equivalence #CSharp

借用一下里面直接的结果（过程很长，而且 Lambda calculus 比较需要一些时间 beta-reduction...）：
So (IsNotHalting IsNotHalting) is reduced to True, which means IsNotHalting halts with IsNotHalting.

Therefore, if IsHalting exists, it leads to IsNotHalting with the following properties:

+ If IsNotHalting halts with IsNotHalting, then IsNotHalting does not halt with IsNotHalting
+ If IsNotHalting does not halt with IsNotHalting, then IsNotHalting halts with IsNotHalting.

This proves IsNotHalting and IsHalting cannot exist.

👆 一言蔽之：如果能定义出函数 停机？，就能定义出一个不停机？函数

(define 不停机？
  λf. If (停机？ (f f))
    (λx. (eternity))
    (λx. True))

然后，如果

+ (停机？ (不停机？ 不停机？)) 是停机的（True），则它反而不停机
+ (停机？ (不停机？ 不停机？)) 是不停机的（False），则它反而是停机的


枚举停机函数可以给出的任何答案（True，False）都无法给出让 (停机？ (不停机？ 不停机？)) 满足其定义的结果
所以就无法回答这个问题。这其实是逻辑问题。

至于 Drakeet 开始提出的那个问题呢，涉及到偏序理论，明天我会解释一下。

—
5 没有被手动排序过，5 排在 1 前面，4 被手动排序过，4 也在 1 前面，但 5 和 4 却无法得出谁在谁前

#doge 已经用上了 Doge 提供的 proxy!

via Electron-ssr

有了汪的 proxy，不用再害怕 tg 的数码狗 MTProto proxy 爆炸了。

#geekapk 我也不是不想继续 github.com/duangsuse/GeekApk(肯定要重写的), 只是现在真的没有时间啊，哪怕写了后端，服务也部署了（虽然都很幼稚，我该去学学 J2EE AS 架构、JPA、JTA、JAX-RS 什么的）
没有 Android 客户端依然是白搭，肯定需要至少十天时间我才敢动键盘。