存在更智能的自动机

扎卡里·蔡斯是牛津大学本·格林的研究生。Chase已经解决了一些有趣的问题-查看他的网站了解更多细节。他的导师因其出色的工作而闻名--特别是在加法组合学方面。一个例子是他与陶渊明的合作，证明了这一令人惊叹的说法：

今天我们想报道蔡斯的新论文，这个问题我们以前已经讨论过两次了。

但首先，肯想说一些关于牛津的事，早在格林到来之前，他就是在牛津获得学位的。

格林于2013年搬到牛津。他拥有与马格达伦学院相关的教授职位。当我1981年开始在牛津时，我(肯)还不认识他。这会很难，因为格林当时只有4岁。但我确实认识十几岁的露丝·劳伦斯(Ruth Lawrence)，当她开始在那里工作时，甚至有一次参加了一场部门槌球比赛，其中包括布莱恩·伯奇(Bryan Birch)，在那场比赛中，布莱恩·伯。劳伦斯在1983年12岁时加入圣休学院。

在过去的六年里，牛津比以前更多地属于迪克和我的心思。2012-2015年Joël Ouakine在那里的时候，我们都是他的客人。牛津大学已经建立了一个量子计算的前线小组，这与大卫·多伊奇作为创始人的角色是从那里开始的-请注意我最近这篇帖子中间的故事。

最近，牛津大学因开发一种前景看好的新冠肺炎疫苗而成为新闻焦点。ChAdOx1在维基百科候选疫苗名单中名列前茅，并已进入最终试验，尽管在批准广泛使用之前仍有一个漫长的评估过程。

在此之前，牛津大学3月份的一项建模研究提出了一个问题，即是否还有更多的人在没有症状或任何知识的情况下患有新冠肺炎。从那时起，这种可能性就被比作“暗物质”假说，不只是现在关于新冠肺炎的假说，而是十年前和之前的假说。

一个主要的支持论点是，如果假设为真，一大类数学模型可以用更高的相对可能性来拟合。在物理学推理方法引发争议的更广泛背景下，我一直想花时间来评估这一论点，但不幸的是，作弊频率不断上升的在线国际象棋占据了所有可支配的时间，甚至更多。

给定两个不同长度的二进制字符串，总有一个有限状态确定自动机(FSA)接受一个而拒绝另一个。这样的机器能有几个状态呢？

这称为分词问题(SWP)。这里我们只考虑二进制字符串。

约翰·罗布森证明了状态就足够了--我们抑制了任何对数因子。有些人喜欢把这个写成。Chase将其改进为：

定理2对于任何不同的，都有一个有限状态确定自动机，它的状态可以接受，但不能接受。

我们之前在GLL上两次讨论过这个问题。我们在这里讨论了背景和初步结果。最初的问题是由于帕维尔·戈拉尔奇克和瓦茨拉夫·库贝克。他们证明了一个上界，那就是。然后我们越过了罗布森在这里的边界。最好的上界是罗布森的结果，直到蔡斯出现。

所有的SWP方法似乎都有一个共同的主线。他们找到一些“散列”函数族，以便：