精华内容
下载资源
问答
  • 图灵计算理论

    千次阅读 2018-06-18 10:38:45
    图灵,又称图灵计算、图灵计算机,是由数学家艾伦·麦席森·图灵(1912~1954)提出的种抽象计算模型,即将人们使用纸笔进行数学运算的过程进行抽象,由个虚拟的机器替代人们进行数学运算。 图灵个...

    前言

    图灵机和计算理论是人工智能乃至整个计算机科学的理论基础,邱奇-图灵论题告诉我们一切可计算过程都可以用图灵机模拟。

    图灵机

    图灵机,又称图灵计算、图灵计算机,是由数学家艾伦·麦席森·图灵(1912~1954)提出的一种抽象计算模型,即将人们使用纸笔进行数学运算的过程进行抽象,由一个虚拟的机器替代人们进行数学运算。

    这里写图片描述

    图灵机指一个抽象的机器,它有一条无限长的纸带,纸带分成了一个一个的小方格,每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态,还有一些固定的程序。在每个时刻,机器头都要从当前纸带上读入一个方格信息,然后结合自己的内部状态查找程序表,根据程序输出信息到纸带方格上,并转换自己的内部状态,然后进行移动。

    每一个会决策、会思考的人都可以被抽象地看成一台图灵机。该模型主要有四要素:输入集合、输出集合、内部状态和固定的程序。如果把人进行抽象,那么输入集合就是所处环境中所看到、听到、闻到、感觉到的一切;输出集合就是人的每一言每一行,还有表情动作;内部状态集合则可以把神经细胞的状态组合看成一个内部状态,所有可能的状态集合将是天文数字。

    人有记忆,图灵机有没有?有,它有了内部状态就可以看成有记忆,内部状态会记录所经历过的世界。

    很多现象似乎都能被图灵机包括,如人了IDE情绪和情感,可以看成某种内部状态,心情好的情绪下,输入和输出是一套规则,而心情不好的情况下,输入输出又是另外一种规则。

    无论是神经元传递信息、变化状态的规律都是固定的,可以被程序化。那么头脑作为神经元的整体,它的运作也比如遵循固定的规则,即程序。正如图灵相信的,人脑也不会超越图灵机模型。

    关于图灵机的学习问题,看似图灵机不包括学习,因为学习就意味着程序的改变,而图灵机不能在运行过程中改变自己的程序。很有可能一个图灵机的规则没有改变,只不过激活了它的某些内部状态,因为发生了本质的变化,尽管给它相同的输入,它却有完全不同的输出,这样看起来似乎它会学习了,虽然图灵机的程序一点都没变。

    通用图灵机存在吗

    是否存在一台万能图灵机能模拟其他所有图灵机?这台万能图灵机就是通用图灵机,把输入x和图灵机m信息都一起输入到通用图灵机,就能计算出一个结果o,这样便可以模拟任何一台图灵机。

    图灵机m信息其实就是编码,通过编码可以将事物进行编号,将所有图灵机进行编码后每个图灵机就有了描述信息,如果某台图灵机的编码为m,输入为x,则将两者合并一起输入到万能图灵机中,计算得到结果。

    停机问题

    尽管图灵机很强大,但它也有解决不了的问题,比如停机问题。通俗地讲,停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题:是否存在一个程序P,对于任意输入的程序w,能够判断w会在有限时间内结束或者死循环。

    1936年图灵已经证明了这样的程序是不存在的。

    从停机问题中可以看到的确存在人类能构造出来而图灵机解决不了的问题,也就是计算机不能解决的问题,这类问题是不可计算的。停机问题揭示了宇宙中的某种共性,所有计算机解决不了的问题本质上讲都和图灵停机问题是计算等价的。相似问题还包括是否存在一个程序能检测所有程序会不会出错。

    停机问题也喝复杂系统的不可预测性有关,存不存在一个程序接收某个复杂系统的规则,然后输出结果?答案是不可能。所以得到一个结论是我们要想弄清楚某个复杂系统运行结果,唯一的办法就是人为去编程实际运行后才能得到结果。这也说明了某些事机器做不了而人类能实现。

    超越图灵计算理论

    一个固定的程序不可能超越图灵计算理论的限制,但如果一个程序能在每时每刻都变化使之不再是原来的自己,那么就可以超越图灵计算理论。就好比人类每时每刻都经过细胞更新使得不再是原来的自己,所以人类超越图灵计算理论。这也就是说,人们没办法通过编写一个固定的程序来实现大脑功能。要实现真正的人工智能,就需要一个能不断改变自己的程序,而且这种改变也不是一个固定的程序。

    ————-推荐阅读————

    我的2017文章汇总——机器学习篇

    我的2017文章汇总——Java及中间件

    我的2017文章汇总——深度学习篇

    我的2017文章汇总——JDK源码篇

    我的2017文章汇总——自然语言处理篇

    我的2017文章汇总——Java并发篇


    跟我交流,向我提问:

    这里写图片描述

    公众号的菜单已分为“读书总结”、“分布式”、“机器学习”、“深度学习”、“NLP”、“Java深度”、“Java并发核心”、“JDK源码”、“Tomcat内核”等,可能有一款适合你的胃口。

    为什么写《Tomcat内核设计剖析》

    欢迎关注:

    这里写图片描述

    展开全文
  • 摘要:本文详细介绍如何利用MATLAB实现手写数字的识别,其中特征提取过程采用方向梯度直方图(HOG)特征,分类过程采用性能优异的支持向量(SVM)算法,训练测试数据集为学术及工程上常用的MNIST手写数字数据集,...

    演示动图

    摘要:本文详细介绍如何利用MATLAB实现手写数字的识别,其中特征提取过程采用方向梯度直方图(HOG)特征,分类过程采用性能优异的支持向量机(SVM)算法,训练测试数据集为学术及工程上常用的MNIST手写数字数据集,博主为SVM设置了合适的核函数,最终的测试准确率达99%的较高水平。根据训练得到的模型,利用MATLAB GUI工具设计了可以手写输入或读取图片进行识别的系统界面,同时可视化图片处理过程及识别结果。本套代码集成了众多机器学习的基础技术,适用性极强(用户可修改图片文件夹实现自定义数据集训练),相信会是一个非常好的学习Demo。本博文目录如下:

    ➷点击跳转至文末所有涉及的完整代码文件下载页☇

    代码介绍及演示视频链接:https://space.bilibili.com/456667721/(正在更新中,欢迎关注博主B站视频)


    前言

        机器学习中支持向量机(SVM)算法可谓是个超级经典,也许很多人倾向于使用深度神经网络解决问题,但在博主看来选择何种算法应该取决于具体的机器学习任务,对于复杂程度不高、数据量较少的任务,也许经典的机器学习算法能够更好地解决问题。手写数字识别这一任务要求正确分类出0-9的手写数字图片,最常用的数据集是MNIST,该数据集也是众多论文中经常用来测试对比算法的对象。博主想说的是其实SVM也可以很好地解决这一问题,本文介绍的代码就可以实现99%的测试准确率,所以想借此为大家提供一个学习的Demo共同交流。

        博主之前也曾写过两篇利用SVM进行分类的博文:基于支持向量机的图像分类(上篇)基于支持向量机的图像分类(下篇:MATLAB实现),详细介绍了特征提取的基本技术和支持向量机的原理,亦可供大家参考。本文给出了MATLAB实现的完整代码供大家参考,有基础的读者可按照文中的介绍复现出完整程序;对于想获取全部数据集及程序文件的朋友,可以点击提供的下载链接获取可直接运行的代码,原创不易,还请多多支持了。如本文对您有所帮助,敬请点赞、收藏、关注!


    1. 效果演示

        找资料的大伙时间宝贵,为了方便大家了解项目,我们老规矩先上效果演示,GUI界面有几个主要功能:通过手写板写入数字进行识别;利用文件浏览器选取一张手写数字的图片进行识别;同步可视化处理过程中的图像,显示最终识别结果。GUI界面如下:

    GUI界面展示图
        在手写板中写入数字后可点击下方保存按钮保存为图片文件,手写输入及读图输入及保存功能的演示动图如下图所示。右侧为图像原图、灰度化处理、二值化处理及特征提取后的图像,方便了解识别的处理过程:

    动图演示
        本项目所有功能均已在MATLAB R2020b中测试通过,更多演示细节敬请前往博主B站观看演示视频,视频具体演示程序运行效果并介绍如何使用代码,欢迎关注!


    2. MNIST数据集

        MNIST数据集来自美国国家标准与技术研究所(National Institute of Standards and Technology, NIST)。训练集 (Training Set) 由来自250个不同人手写的数字构成,其中50%是高中学生,50%来自人口普查局的工作人员;测试集(Test Set) 也是同样比例的手写数字数据。

    MNIST数据集
        MNIST数据集可在 http://yann.lecun.com/exdb/mnist/获取,但由于访问外网下载速度很慢,博主已将该数据集打包上传至百度网盘,大家可以通过博主前面发布的博文:深度学习常用数据集介绍与下载(附网盘链接)进行下载。MNIST数据集包含了四个部分:

    • Training set images:train-images-idx3-ubyte.gz (9.9MB,解压后47MB,包含60000个样本)
    • Training set labels:train-labels-idx1-ubyte.gz(29KB,解压后60KB,包含60000个标签)
    • Test set images:t10k-images-idx3-ubyte.gz (1.6MB,解压后7.8MB,包含10000个样本)
    • Test set labels: t10k-labels-idx1-ubyte.gz(5KB,解压后10KB,包含10000个标签)

        将下载后的数据集文件放在一个文件夹下,用于后续处理,MNIST数据集文件如下图所示:

    数据集文件
        由于MNIST的原始文件并非常见的图片格式,因此为了方便后续处理,我们先将这几个文件转化为mat文件,然后逐个读取转换为图像矩阵并保存为图片文件。值得注意的是,我们需按照每条样本数据的标签将其分别放置在不同的文件夹中,如下方式在train文件夹中创建0-9的文件夹用来存放要写入的对应标签的图片:

    子文件夹
        这里写一个小脚本将数据集图片按标签存入对应文件夹中,其中的mat文件为读取原始数据并转存后的数据集,MNIST每张图片的尺寸均为28×28,所以可以先通过reshape恢复数据尺寸,然后利用imwrite函数写入文件中(路径为对应标签的子文件夹),该部分代码如下:

    clear
    clc
    % P = loadMNISTImages('mnist/train-images.idx3-ubyte');
    % T = loadMNISTLabels('mnist/train-labels.idx1-ubyte');
    load('test_data.mat', 'test_X')
    load('test_label.mat', 'test_Y')
    load('train_data.mat', 'train_X')
    load('train_label.mat', 'train_Y')
    load('validation_data.mat', 'validation_X')
    load('validation_label.mat', 'validation_Y')
    % 遍历每张图片
    disp('现在将训练数据保存为图片文件格式')
    for i = 1:length(train_X)
        img = reshape(train_X(i, :), 28, 28); % 转换成28*28的图片
        img = img';
        imwrite(img, ['./mnist/train/', int2str(train_Y(i)), '/', int2str(i), '.jpg']);
        disp(i);
    end
    % 遍历每张图片
    disp('现在将测试数据保存为图片文件格式')
    for i = 1:length(test_X)
        img = reshape(test_X(i, :), 28, 28); % 转换成28*28的图片
        img = img';
        imwrite(img, ['./mnist/test/', int2str(test_Y(i)), '/', int2str(i), '.jpg']);
        disp(i);
    end
    

        处理后的子文件夹中将存放对应的图片文件,其中两个子文件夹的截图如下图所示:

    子文件夹详情
        数据集准备完毕,现在可以通过文件夹读取图片了。在MATLAB中可使用imageDatastore函数方便地批量读取图片集,它通过递归扫描文件夹目录,将每个文件夹名称自动作为图像的标签,该部分代码如下:

    % 给出训练和测试数据路径,利用imageDatastore载入数据集
    syntheticDir   = fullfile('data','mnist', 'train');
    handwrittenDir = fullfile('data','mnist', 'test');
    
    % imageDatastore递归扫描目录,将每个文件夹名称自动作为图像的标签
    trainSet = imageDatastore(syntheticDir,   'IncludeSubfolders', true, 'LabelSource', 'foldernames');
    testSet  = imageDatastore(handwrittenDir, 'IncludeSubfolders', true, 'LabelSource', 'foldernames');
    

        至此训练和测试数据集分别被存放在trainSettestSet变量中,可以简单查看训练和测试集每类标签的样本个数,显示代码如下:

    trainSetDetail = countEachLabel(trainSet) % 训练数据
    testSetDetail = countEachLabel(testSet) % 测试数据
    

        执行以上代码运行结果如下:

    查看各类文件个数
        下面读取几张训练和测试集的图片,显示原始图片帮助我们清楚该数据集的实际情况,按照两行显示:第一行为训练图片,第二行为测试图片,该部分代码如下:

    figure;
    % 显示训练、测试图片(第一行是训练图片、第二行是测试图片)
    subplot(2,5,1);imshow(trainSet.Files{4417});
    subplot(2,5,2);imshow(trainSet.Files{23696});
    subplot(2,5,3);imshow(trainSet.Files{31739});
    subplot(2,5,4);imshow(trainSet.Files{46740});
    subplot(2,5,5);imshow(trainSet.Files{54784});
    subplot(2,5,6);imshow(testSet.Files{53});
    subplot(2,5,7);imshow(testSet.Files{4572});
    subplot(2,5,8);imshow(testSet.Files{5163});
    subplot(2,5,9);imshow(testSet.Files{8381});
    subplot(2,5,10);imshow(testSet.Files{9549});
    

        执行该代码可以看到如下的运行结果:

    数据集显示
        在提取特征前我们对图片进行一些必要的预处理操作,首先读取图片后进行灰度化,然后进行二值化处理,以方便后续的特征提取。这里我们将原始图片和二值化后的图像显示在一个窗口中,其代码如下:

    exampleImage = readimage(trainSet, 31739);
    if numel(size(exampleImage))==3
            exampleImage = rgb2gray(exampleImage);   % 灰度化图片
    end
    
    processedImage = imbinarize(exampleImage);
    
    figure;
    subplot(1,2,1)
    imshow(exampleImage)
    title('原始图像')
    
    subplot(1,2,2)
    imshow(processedImage)
    title('二值化后图像')
    

        执行该代码可以看到如下的原始图像与二值化后的对比结果:
    二值化对比结果


    3. HOG特征提取

        真正用于训练分类器的数据并不是原始图片数据,而是先经过特征提取后得到的特征向量,这里使用的特征类型是HOG,也就是方向梯度直方图。所以这里重要的一点是正确提取出HOG特征,extractHOGFeaturesMATLAB自带的HOG特征提取函数,该函数不仅可以有效提取特征,还可以返回特征的可视化结果以方便展示。这里通过调整每个细胞单元的尺寸大小实现不同尺寸的特征提取,可以通过可视化的结果看到细胞单元的尺寸对图像的形状信息量的影响:

    img = readimage(trainSet, 31739);
    
    % 提取HOG特征,并进行HOG可视化
    [hog_2x2, vis2x2] = extractHOGFeatures(img,'CellSize',[2 2]);
    [hog_4x4, vis4x4] = extractHOGFeatures(img,'CellSize',[4 4]);
    [hog_8x8, vis8x8] = extractHOGFeatures(img,'CellSize',[8 8]);
    
    % 显示原始图片
    figure; 
    subplot(2,3,1:3); imshow(img);
    title('原始图片');
    
    % 可视化HOG特征
    subplot(2,3,4);  
    plot(vis2x2); 
    title({'CellSize = [2 2]'; ['Length = ' num2str(length(hog_2x2))]});
    
    subplot(2,3,5);
    plot(vis4x4); 
    title({'CellSize = [4 4]'; ['Length = ' num2str(length(hog_4x4))]});
    
    subplot(2,3,6);
    plot(vis8x8); 
    title({'CellSize = [8 8]'; ['Length = ' num2str(length(hog_8x8))]});
    

        通过以上代码我们分别提取了2×24×48×8三种尺寸的HOG特征,其运行的可视化结果如下:
    不同尺寸HOG特征
        从以上结果可以看出2×2的细胞尺寸会编码更多的形状信息,这会显著增加HOG特征向量的维数,相反8×8的细胞尺寸得到的特征量最少。这其实是一个需要调试的参数,一方面应该对足够的空间信息进行编码,另一方面需要减少HOG特征向量的维数,为此可以选择4×4的细胞大小。当然读者还可以通过反复根据分类器训练和测试的效果来调整HOG特征的相关参数,以实现最佳参数设置。


    3. 训练和评估SVM分类器

        下面我们使用以上提取的HOG特征训练支持向量机,以上的代码只是提取了一张图片的特征,训练前我们对整个训练数据集提取HOG特征并组合,为了方便后面的性能评估,这里对测试数据集也进行特征提取:

    cellSize = [4 4];
    hogFeatureSize = length(hog_4x4);
    
    % 提取HOG特征
    tStart = tic; 
    [trainFeatures, trainLabels] = extractHogFromImageSet(trainSet, hogFeatureSize, cellSize); % 训练集特征提取
    [testFeatures, testLabels] = extractHogFromImageSet(testSet, hogFeatureSize, cellSize);    % 测试集特征提取
    
    tEnd = toc(tStart);
    fprintf('提取特征所用时间:%.2f秒\n', tEnd);
    

        由于图片数量众多,提取特征过程尚需一定时间,这里对训练集、测试集提取过程进行计时,因计算机算力不同,执行时间可能会不一致。以下代码中extractHogFromImageSet函数为自定义函数,封装了前面所提到的图像灰度化、二值化和HOG特征提取的代码,可以方便我们复用代码,使得程序更加简洁。

    cellSize = [4 4];
    hogFeatureSize = length(hog_4x4);
    
    % 提取HOG特征
    tStart = tic; 
    [trainFeatures, trainLabels] = extractHogFromImageSet(trainSet, hogFeatureSize, cellSize); % 训练集特征提取
    [testFeatures, testLabels] = extractHogFromImageSet(testSet, hogFeatureSize, cellSize);    % 测试集特征提取
    
    tEnd = toc(tStart);
    fprintf('提取特征所用时间:%.2f秒\n', tEnd);
    

        运行以上代码结果如下:

    提取特征所用时间:181.59秒
    

        构建支持向量机模型,利用提取的训练集特征进行训练。首先利用templateSVM函数构建支持向量机模板参数,选择polynomial核函数,执行标准化处理数据,显示训练过程;利用fitcecoc函数执行训练过程,其代码如下:

    % 训练支持向量机
    
    t = templateSVM('SaveSupportVectors',true, 'Standardize', true, 'KernelFunction','polynomial', ...
        'KernelScale', 'auto','Verbose', 1);      % 利用polynomial核函数, 标准化处理数据,显示训练过程(verbose取0时取消显示)
    
    tStart = tic; % 计时开始
    classifier = fitcecoc(trainFeatures, trainLabels, 'Learner', t); % 训练SVM模型
    tEnd = toc(tStart);
    fprintf('训练模型所用时间:%.2f秒\n', tEnd);
    

        以上代码开启了训练过程信息显示,训练过程中显示信息如下:

    训练过程展示

    训练模型所用时间:104.96秒
    

        等待训练完成,我们可以使用训练好的分类器进行预测,这里先利用测试集评估模型并计算分类评价指标,对测试集进行预测的代码如下:

    tStart = tic;
    
    % 对测试数据集进行预测
    predictedLabels = predict(classifier, testFeatures);
    
    tEnd = toc(tStart);
    fprintf('模型对测试集进行预测所用时间:%.2f秒\n', tEnd);
    

        运行结果如下:

    模型对测试集进行预测所用时间:5.18秒
    

        得到了预测结果,可以使用混淆矩阵评估结果,以下代码首先计算混淆矩阵结果,然后将结果打印出来:

    % 使用混淆矩阵评估结果
    confMat = confusionmat(testLabels, predictedLabels);
    dispConfusionMatrix(confMat); % 显示混淆矩阵
    

        运行结果如下:

    混淆矩阵打印结果
        以上代码显示了混淆矩阵的结果,但可能还不够直观,下面绘制混淆矩阵图帮助更好了解模型性能:

    % 绘制混淆矩阵图
    plotconfusion(testLabels, predictedLabels);
    

        运行代码后显示混淆矩阵图如下图所示,每行对角线上的网格(绿色网格)处显示了某类样本预测正确的数目及其占比。右下角网格表示分类的准确率,可以看出该分类器具有98.9%的总体分类准确率。
    混淆矩阵图
        分类准确率还可以通过以下代码进行计算:

    accuracy = sum(predictedLabels == testLabels) / numel(testLabels);
    fprintf('模型在测试集上的准确率:%.0f%%\n', accuracy*100);
    

        同样可以计算出预测的准确率,这里四舍五入取整可得以下结果:

    模型在测试集上的准确率:99%
    

        通过测试集评估结果,可以看出采用核函数的支持向量机准确率为99%,其性能已逼近深度卷积神经网络。得到了一个性能优良的分类器,接下来便可以利用模型设计一些有意思的东西了。为此我将该模型用于实际的手写数字识别中,以下是在MATLAB GUI工具中设计的界面,如若读者反响热烈,后期将很快更GUI的设计介绍,还请关注了!

    GUI界面


    下载链接

        若您想获得博文中涉及的实现完整全部程序文件(包括数据集,m, UI文件等,如下图),这里已打包上传至博主的面包多平台和CSDN下载资源。本资源已上传至面包多网站和CSDN下载资源频道,可以点击以下链接获取,已将所有涉及的文件同时打包到里面,点击即可运行,完整文件截图如下:

    文件夹详情

    注意:本资源已经过调试通过,下载后可通过MATLAB R2020b运行;训练主程序为main_showData.mlxDigitClassify_HOG_SVM.m文件,测试程序可运行testImage.mlx,要使用GUI界面请运行DigitClassifyUI.m文件(脚本文件可直接运行);其它程序文件大部分为函数而非可直接运行的脚本,使用时请勿直接点击运行!➷➷➷

    完整资源下载链接1博主在面包多网站上的完整资源下载页

    完整资源下载链接2https://mianbaoduo.com/o/bread/YZeUkplu

    注:以上两个链接为面包多平台下载链接,CSDN下载资源频道下载链接稍后上传。

    代码使用介绍及演示视频链接:https://space.bilibili.com/456667721/(尚在更新中,欢迎关注博主B站视频)


    结束语

        由于博主能力有限,博文中提及的方法即使经过试验,也难免会有疏漏之处。希望您能热心指出其中的错误,以便下次修改时能以一个更完美更严谨的样子,呈现在大家面前。同时如果有更好的实现方法也请您不吝赐教。如果本博文反响较好,其界面部分也将在下篇博文中介绍,所有涉及的GUI界面程序也会作细致讲解,敬请期待!

    展开全文
  • 计算,是个研究比图灵机计算能力更强的计算能力的计算机器的理论计算机科学分支。 主要有以下部分模型:   A.谕示. (Oracle Machine) 带“黑箱”的图灵。由图灵本人亲自提出,“黑箱”就是个谕示...

    有,而且还不少。他们被称为超计算(Hyper computation)模型。

    超计算,是一个研究比图灵机计算能力更强的计算能力的计算机器的理论计算机科学分支。

    主要有以下部分模型:

     

    A.谕示机. (Oracle Machine) \clubsuit

    带“黑箱”的图灵机。由图灵本人亲自提出,“黑箱”就是一个谕示,经过一个谕示就可以得到一个问题的判定结果。所有 Hypercomputation 的“原型机”。后来的大部分计算模型都是基于谕示机的概念,将其他特性引入图灵机中使其不受先前的计算能力限制而得到新的模型。

     

    B.Blum–Shub–Smale machine. \clubsuit

    可以在实数域内计算并可以储存无限精度的实数(而经典图灵机只能储存可计算数。)而它对应的计算时间是离散的。但是,如果图灵-丘奇论题在我们宇宙中为真,那么宇宙中就不存在实数,只存在可计算数。

    P.S. Blum–Shub–Smale machine 的配置是一个四元组: (k,r,w,x) ,其中 k 是当前执行指令的数量, r 和 w 是复制寄存器(copy registers), x 是存储在 BSS machine 所有寄存器内的内容。机器的计算由配置 (0,0,0,x) 开始,在 k = N (N 为 indexed)时结束计算。而 x 的最终内容被认为是该机器的输出。

    更加具体地,我们假设 R 是一个 ring,BSS machine 在 R 上。 \mathcal{N} =\left \{ 1,...,N \right \} 是 BSS machine 的节点(nodes)集。 \mathcal{S} 为机器的状态空间, \mathcal{S\times N} 为机器的 full space。而一个函数 H 来自 \mathcal{S\times N}\rightarrow\mathcal{S\times N} ,且映射至每一对 \left( \eta,x \right)\rightarrow\left( \eta^{'} ,x^{'} \right)。这个函数 H 可以定义 BSS machine 的停机集 \Omega _{M}

    一个函数 \pi_{\mathcal{N}}:\mathcal{N\times S\rightarrow N} 为在 \mathcal{N} 上的 full spaces 的射影(projection)。然后其节点序列 1,\eta^{1},...,\eta^{k} 其中 \eta^{k}=\pi_{\mathcal{N}}\left( z^{k} \right) 。如果在时间 Tu\in\mathcal{S} 且满足 z^{T}=\left(N,u \right) 则有限序列 z^{0},...,z^{T} 为 BSS machine 的停机计算。而 BSS machine 的停机时间 T_{M}\left( x \right) 为:

    T_{M}\left( x \right)=\mathrm{min}\left\{ T_{i}|z^{T_{i}} =\left( N,u_{i} \right)\right\}

     

    C.量子计算机.

    在量子物理中,对一个系统状态的完整描述需要使用复数,即量子系统的状态是一个位于 2^{n} 维向量空间中的一个点。右括向量 |x\rangle 意味着 x 是一个(纯)量子态。与这个量子系统相关的希尔伯特空间是 2^{n} 个量子态作为基向量的复向量(complex vector space)空间,系统在任何时候的状态由这个希尔伯特空间中的一个单位长度向量表示。

    同时系统的叠加态可表示为: \sum_{i=0}^{2^{n}-1}{a_{i}|S_{i}\rangle }

    其中振幅(amplitudes) a_{i} 为满足 \Sigma _{i}|a_{i}|^{2}=1 的复数,每一个 |S_{i}\rangle 为希尔伯特空间中的一个基向量。

    为了使用物理系统进行计算,我们必须能够改变系统的状态。量子力学定律只允许状态向量的幺正转换。一个幺正矩阵的共轭转置(conjugate transpose)等于它的逆矩阵,并且要求状态变换由酉矩阵来表示,这就保证了得到所有可能结果的概率之和为1。同时量子电路(和量子计算机)的定义只允许局部幺正转换;也就是说,对固定数目的比特进行酉(幺正)变换。

    值得注意的是:量子计算机的计算能力在本质上与图灵机等价,但在计算复杂度上可以优于图灵机(如果这也算是计算能力的话。)。现实中的量子计算机的计算能力可以在多项式时间内解决 BQP ,并没有想象中的那么强。

    但是,尽管目前可以通过结构与算法优化使计算能力不断提高,但量子计算机的计算能力还是有真正的上限的:即布莱梅曼极限(Bremermann's limit)。在量子物理框架下,我们宇宙中所有物质的计算能力都不可能超过每千克 \frac{c^{2} }{\hbar } bits/s(h为普朗克常数,c为光速)这也是量子计算机真正无法逾越的计算速度极限。而且你也不可能真正地达到该极限,因为所需能量会使你的计算机直接坍塌成一个黑洞。

    最后值得一提的是,只要对量子力学中算符的线性要求做些微的放宽,例如,温伯格引入的非线性算符(这些工作出现在温伯格试图研讨的所谓非线性量子力学中)得到允许,则我们可以在新型量子计算机上用多项式时间求解 PSPACE 完全问题( NP 完全问题自然不在话下)。

    但是: 由于非线性的引入一定会同时容许超光速通信和违背热力学第二定律的结果,所以提议基本是不可行的。

     

    D.相对论时间效应 \clubsuit

    在相对论中,不同物体参考系的时间流逝不一样,如果我们能让计算机参考系在时间流逝上快很多,那我们也变相得解决了这个问题。

    一台计算机留在地球上让它做一个复杂的计算问题,然后操作者登上一个航天器,加速到接近光速,一段时间后减速再返回地球。根据:

     

    \Delta t为地球计算机的时间,\Delta \tau为操作者的时间,c 为光速。 如果操作者可以找到电脑并且它还在运行的话,就可以知道那个复杂问题的答案了。

    不过这要使计算机进行指数级的加速,必须让速度指数级接近于光速,这也意味着所需要的能量指数级增长,而因为能量密度不可能大于黑洞,这也意味着计算机的大小必须指数级增长,某种程度上来说就是 EXPSPACE ,这是不可取的(建造指数级数量的计算机同时计算可达到同样效果)。

     

    E. 封闭类时曲线计算机. \clubsuit

    依靠广义相对论中拥有闭合时间曲线的封闭类时曲线 (closed timelike curve, CTC) 时空来计算给计算机配一台时间机器。

     

    在计算理论中,人们比较感兴趣的问题之一是,NP 问题,比如哈密尔顿回路问题(判断一个图是否有圈经过每个顶点恰好一次),是否可以在多项式时间内被解决。然而即使是引入了量子计算后,这个问题也一直悬而未决。

     

    20世纪后期,学者们开始探讨是否存在在计算能力上可以超越量子计算的模型以及它们的物理实现可能性。

     

    物理学家 Deutsch 提出,如果我们在时间本身上做手脚呢?

    于是就有了利用封闭类时曲线来进行加速计算的提议。

    但是,利用 closed timelike curve 来做时间旅行的话,就不得不面对一个悖论,即祖父悖论。

    目前解决祖父悖论的方法有很多,封闭类时曲线计算机采用的是这个(虽然有很多科学家并不认同这种解决方法。):

    你回到过去杀掉祖父的可能性为 50%,于是你祖父生下你的父母可能性也为 50%,这样你回到过去的可能性就是 50%,如此循环。于是你和你的祖父其实都是“存在”和“不存在”的叠加,可能性各是 50% ( \frac{1}{2} )。

    那么为什么是 50% 的可能性呢?试想,如果你有 1/3 ( \frac{1}{3} )的可能性回去杀掉祖父,那么他生下你父母的可能性就变为 2/3,于是你回到过去杀人的可能性就是 2/3( \frac{2}{3} ),而不是我们所假设的 1/3。这样就出现了因果不连续。大自然不允许这样的情况存在(出现悖论),所以它强迫你必须以 50% 的可能性存在。也就是说,如果你进行了“回到过去杀掉祖父”这一行动,那么大自然说,你的存在必然是 50% 的可能。在量子机制框架下,CTC是自洽的。简单的解释下,就是这个世界是个概率空间,以马尔可夫过程的方式进行运作,如果每次新的概率分布和原来的一样,马尔可夫过程的稳定分布则是一组解。那么,这样就可以避免祖父悖论了。没有任何矛盾。

    (补充内容)也就是说,如果我们让 |\varphi \rangle 为"更年轻"版载体粒子的初始态,让 \hat{\rho } 为与其互动的"更老"版载体粒子的密度算符。然后进入一区域这两个粒子进行相互作用的联合密度算符是 :

    |\varphi \rangle \langle\varphi |\otimes \hat{\rho }

    而两粒子在相互作用后的密度算符为: U\left ( |\varphi \rangle \langle\varphi |\otimes \hat{\rho } \right )U^{\dagger }

    而量子一致性条件要求, 当它离开交互区域时, 更年轻版的粒子的密度算子(符)与它进入交互区域时的更老版相同:

     

    这个 \frac{1}{2}为 Fixed-point,即不动点。这个不动点确保了自然的运行依然符合因果定律。而且大自然会以某种神奇的机制自动的寻找这个“不动点”,以使整个系统因果连续(历史自治)。

     

    封闭类时曲线计算机具体的计算原理是这个:"莎士比亚戏剧"。

    一个人抄下莎士比亚全集,然后回到过去将其交给莎士比亚本人。

    于是莎士比亚全集就这么凭空产生了。

    原因是,为了保证“那个人”能够“阅读到”莎士比亚全集(否则他不可能知道有这么个东西),它必须足够出名。而既然他已经带着它回到过去,那么为了维护因果连续,大自然这个系统为我们“写”了一个足够出名的东西出来。这个东西就是莎士比亚全集,即不动点。

    当然,系统同时也曾经尝试过无数其他的“作品”,甚至一些不成话的乱码。

     

    这样一台计算机,能够随时进行指向过去的时间旅行。并且,它能够利用我前面提到的封闭类时曲线(CTC)来解决一些一般情况下非常难以解决的问题。

    具体地,比如说“大数分解”问题。

    首先,我得给它一个大数,并期望它输出这个数的任一个因数(除了1)。一般来说,普通计算机也许会在运行100万年以后给出答案(如果它一直不死机),而封闭类时曲线计算机却能在短短1秒钟之内(也许更短)给出答案。

    它怎样工作呢?首先,在输入数据 A 之后,它记下这个时刻 t ,同时,它得到了一个神秘的输入数据 x。然后它检查“ x 是否是 A 的因数 ”。如果不是,则 x = x+1,同时如果 x > A ,则 x = 2。之后输出 x,并利用封闭类时曲线进行时间旅行回到 t 时刻,将 x 输入自身。

    很明显,这是一个循环,只不过这个循环运行在时间上。而大自然为了维护因果连续,会不断的做这个循环,寻找这个让因果连续和历史自治的不动点,即 "x 是 A 的因数" ;直到输入的 x 与输出的 x 相同为止,即直到 x 确实是 A 的因数为止。所以在我们看来,这台电脑会在1秒钟内直接输出我们想要的 x。

    这就相当于是这个时间机器的时间循环帮我们计算了所有可能性,在一秒钟内的不断循环计算之内给出了答案。也就是说,如果封闭类时曲线存在,计算机可以“强迫”自然去解决复杂的组合问题,仅为了让宇宙的历史保持一致(比如,去阻止类似祖父悖论这样的东西的出现)。而且在这些复杂的组合问题里面就包括了 PSPACE(包括 PSPACE -complete , NP 类型,也包括了 NP-complete ),甚至可能包涵图灵不可计算问题。

     

    另外,记P_{CTC} , 为允许封闭类时曲线的多项式时间可计算的问题。BQP_{CTC} 是结合量子计算机时多项式时间可计算的问题。它们俩能解决地的计算问题级别是等价的:都可以解决PSPACE。

    如果 Deutsch 的封闭类时曲线可以允许计算任意长度的字符串,则封闭类时曲线计算机可以判定停机问题。

     

    P.S. 补充说明,以上的 CTC 计算机的计算原理和计算能力是基于 Deutsch 的模型。除此之外,学术界还存在着其他解决祖父悖论的方法,在此之上提出了另一种 CTC 计算机模型。

    2009年,另一位物理学家 Seth Lloyd 给出了利用另一种 CTC 模型进行计算的方法,该模型中封闭类时曲线的存在是基于量子态隐形传输和事后选择(post-selection)算法。与 Deutsch 的封闭类时曲线不同的是,Deutsch 的模型会导致相关性破坏效应,即时间旅行者从 Deutsch 的 CTC 出来进入的宇宙,与他在未来的退出(即他之前所在的那个宇宙)无关。相比之下,后选择 CTC 保持了相关性,这样时间旅行者回到他记忆中的同一个宇宙。

    Seth Lloyd 的模型解决祖父悖论的方式如下:

    运用 Post-selection 算法能够确保某一特定类型的量子信息态进行隐形传输,而将其他量子信息过滤掉。只有经“后选择”算法认定传输前后能自相一致的量子信息态,才有资格得到这种“通行证”,进行隐形传输,形成一个自治、不产生矛盾的环境状态。而且 Post-selection 会决定只有有限类型的量子态能被远距传输,即在远距传输前原始物体的量子态也被局限了,由于时间旅行的结果属于有限概率,祖父悖论将不可能发生。

    但是,Seth Lloyd 的模型会削弱封闭类时曲线的计算能力。在 Deutsch 模型中,无论是配经典图灵机还是量子图灵机,都可以解决全部 PSPACE。而在 Seth Lloyd 模型中,配经典图灵机只可以解决 BPP_{path} ,配量子图灵机可以解决 PP。

     

    F.我们熟知的神经网络:前提是具有无限精度。 \clubsuit

    在 H. Siegelmann 的框架下,同步演化的处理器连接成的有限大小的神经网络由处理器的同步网络组成,其架构由一个一般性的有向图描述。输入字符通过 M 个输入通道传输,每次传一个。输出端是一个字符流,每个字符由 p 个值表示。图的节点称为神经元。每个神经元把一个单变量函数作用到所有神经元的激活值和外部输入的仿射组合上,以此来更新自己的激活值。

    具体地,更新方式是:

    x_i(t+1) = \sigma\left(\sum_{j=1}^N a_{ij} x_j(t) + \sum_{j=1}^M b_{ij} u_j(t) + c_i\right)\,\,,\,\,i=1,2,3,...

    其中 x_{j} 为激活函数 (function of the activations); u_{j} 为输入; a_{ij},b_{ij},c_{i} 为神经网络的权重。

    其中 \sigma 为饱和线性函数: \sigma(x) = \begin{cases} 0 \quad \text{ if } \,\,\, x < 0\\ x \quad \text{ if }\,\,\, 0\le x\le 1\\ 1 \quad \text{ if } \,\,\, x>1 \end{cases}

    注意,在这里, a_{ij},b_{ij},c_{i} 都为实数而不是有理数;

    具有实权重的神经网络将拥有超越图灵机的计算能力。

    可知:实权重神经网络是一个 nonuniform 模型,它可以在多项式时间内判定 \textrm{P / poly} ;

    然而目前权重神经网络是不可能做到的,因为现实中存在热力学制约和量子基本单位的制约;其实更主要的是热力学层面的限制。

    P.S. 在生物大脑中,神经元之间的信号传递靠离子通道;当缩小神经元,可产生电信号的离子通道也会减少,噪声则会随之增多(由于离子通道太小,仅凭 thermal vibration 便可轻松打开或关闭这些通道;开或关完全是随机的,于是神经噪音便产生了);特别地:当轴突直径为 150 至 200 纳米时,它们已经会产生大量的噪音了。

    存在噪音的神经网络无限精度是不可能的。

     

    G.无限时间图灵机. \clubsuit

    由 Joel Hamkins 和 Andy Lewis 提出。作为芝诺机的泛化模型,可以在计算任务时间内执行超限数计算步骤(例如 \omega.\omega+1...2\omega...\omega ^{2}...\omega ^{\omega }...\varepsilon _{0}...)。在限定的超限序数时间内, 计算机的组态是根据所有之前的组态定义的。当机器进入一个特殊的极限状态(limit-state)时,操作带的方格将取其如下数值:

     

    0, if the square has settled down to 0
    1, if the square has settled down to 1
    1, if the square alternates between 0 and 1 unboundedly often
    

     

    读写头被放回第一个操作带方格上, 然后机器从这个极限状态继续它的计算。如果在某一时刻没有 appropriate step 来执行,则该机器停机。因此, 它可以在有限的计算步骤内停机, 或无限计算步骤内停机, 或继续在超限序数时间内运行, 永不停机。

    无限时间图灵机可以用 \omega 步骤来计算任何递归可枚举函数, 通过将其操作带上的第一个方格设置为 0, 然后开始计算函数。如果 f(n)=1 ,则第一方格字符再设置为1。具体地,如果 f(n)=1,经过\omega 步骤计算后其第一方格数值保留为1; 如果 f(n)=0,经过\omega 步骤计算后其第一方格数值保留为0。类似的方法也计算任何递归可枚举实数。由于无限时间图灵机在计算过程中可以使用它们的全部方格, 因此,它们接受无限输入时 , 也可以产生无限输出。

    更具体地拓展,无限时间图灵机可以用 n\,\cdot\,\omega 计算步骤计算 \Sigma_{n}^{0}\cup\Pi_{n}^{0} ;

    一个 relation \triangleleft \subseteq A\times A 其中 \mathrm{Ord}\left( A \right)=\omega 可以编码一个 x\in\mathbb{R} 而这样对于第 \left(\langle n,k \rangle \right) 位比特来说

    {\displaystyle x={\begin{cases}1,&{\text{if }}\,n\triangleleft k{\text{ holds }},\\0,&{\text{otherwise.}}\end{cases}}}

    \left(\langle. , .\rangle \right) 是一个 bijective pairing function, n,k\in A ,如果 x 对应与一个良序(well-ordering) \triangleleft 。则可定义良序集(set of well-ordering) WO , 而 \Pi_{1}^{1} 可以图灵归约至 WO 而任何的 reducing computable function 是无限时间图灵机可判定的,因为 WO 是无限时间可判定的。所以 \Pi_{1}^{1} 同样是无限时间可判定的。

    结论: \Pi_{1}^{1} 是无限时间图灵机可判定的,同样 \Sigma_{1}^{1} 也是无限时间可判定的。

    无限时间图灵机是图灵机计算时间延长至超限序数的自然延伸。该模型需要在完全连续的(不存在最小时间单位)的时间里进行计算,然而在现实中不可能做到,因为这样该机的读写头的速度会违背相对论速度极限亦或无限长度计算时间。

    P.S. 无限时间图灵机更多的是作为可执行 supertask 的机器的“抽象描述”。

     

    H.模糊图灵机.(Fuzzy Turing Machine) \clubsuit

    模糊图灵机会采用基于模糊逻辑的模糊算法,可以在“不经意间”解决经典图灵机不能解决的“停机问题”。由 Wiedermann 提出并证明了该类型图灵机可以解决不可判定问题,允许非递归函数的计算。

    模糊图灵机的计算本身只要求一个大概的分布,而不要求精确值。精确并不是必须的,从而整个计算过程并不要求离散化,至少对输入不作要求,只要在输出的时候离散化到某几个特定范畴。这样的话,由于计算精度要求带来的约束就可以放宽。

    具体地,一个具有单向磁带的非确定性模糊图灵机是一个九元组(nonuple):

    \mathscr{F}=(Q,T,I,\Delta,␣\,\,,q_{0},q_{f},\mu,*)

    其中:Q 是有限状态集;T 是有限符号集;I 是一个输入符号集,其中 I\subseteq T ; \Delta 是一个转移关系(transition relation)并且它是 Q\times T\times Q\times T\times\left\{ L,N,R \right\} 的子集,机器所采取的每一个操作都与一个元素 \delta\in\Delta 相关联; ␣ \,\in T ⧵ I 是一个空符号(blank symbol); q_{0} 为初始态; q_{f} 为末态;* 是一个 t-norm.

    如果 \mu 是一个从 Q\times TQ\times T \times\left\{ L,N,R \right\} 的部分函数 (partial function)而 T 是一个 Q 的模糊子集,则该模型变为确定性模糊图灵机。

    模糊图灵机所接受的模糊语言的模糊集定义如下:

    L(\mathscr{F})=\left\{ (w,e(w)) | w\, \mathrm{is\,\,accepted\,\,by\,\,\mathscr{F}\,\,with\,\,plausibility\,\,degree}\,\,e(w)\right\}

    \Phi 来表示模糊图灵机可计算的 t-norms;并且: \Phi=\Pi_{1}^{0}\cup \Sigma_{1}^{0} .

    (P.S. 原先被替换的内容可以在 “模糊图灵机的逼近性与通用性”找到)

     

     

    I.广义相对论中的 Malament-Hogarth 时空。 \clubsuit

    这些时空拥有一条奇怪的世界线,世界线的本征时间 (proper time)是无限的,但时空中存在一个 event p ,沿着世界线发生的所有事件都可以包涵于 event p 中的过去有限区间中。这个 event p 称为 Malament-Hogarth event 。

     

    一个标准的 Malament-Hogarth 时空模型是这样的:

    Toy Malament-Hogarth spacetimes

    首先,在 Minkwski 时空 \left( \Re ^{4} ,\eta _{ab} \right),考虑一个紧致集 (compact set)C 且 C\subset M;选定一个位于 M 上的标量场 (scalar field)Ω ,位于紧致集 C 之外且 Ω=1;时空中存在一个 point r 属于紧致集 C,在接近 point r 时,Ω 迅速变为无限。

    则时空 \left( \Re ^{4} -r,\Omega ^{2} \eta _{ab} \right) 是一个 Malament-Hogarth 时空。

    时空中的任何类时曲线在接近 point r 时本征时间将变为无限(图中的 \gamma _{1}),而一条类时曲线在接近时空的 endpoint p 时则它的本征时间却是有限的(图中的 \gamma _{2}),而在 \gamma _{1} 上发生的所有事件都已经成为过去。

    即:在 时空 \left( M,g \right) 中,M 为连贯四维豪斯多夫 C^{\infty } 流形,g 为洛伦兹度规:

    I. 如果存在类时半曲线 (timelike half-curve)\gamma _{1} \subset M

    II.存在一个 event point p,其中:

    \mathrm{event\, \, point\, \,} p\in M , \int_{\gamma_{1}}^{}d\tau=\infty , \gamma_{1}\subset I^{-}\left( p \right)

    其中 \gamma_{1}\subset I^{-}\left( p \right) 表示为 p 的过去区间。则它为 Malament-Hogarth 时空。此外:

    还存在一条未来定向类时半曲线 ( future-directed timelike half curve) :

    \gamma _{2} \subset M

    III.存在一个 event point q ,其中:

    \mathrm{event\, \, point\, \,} q\in I^{-}\left( p \right)\int_{\gamma_{2}\left(q,p \right)}^{}d\tau<\infty

    于是有了以下的提议:

    让一台计算机(图灵机)沿着类时曲线 \gamma _{1} 移动,由于它的本征时间是无限的,图灵机就有时间来进行无限步骤的计算过程。而一个观测者则沿着类时曲线 \gamma _{2} 移动,时间是有限的,当观测者到达 p 时,图灵机的无限计算也已经完成了。

     

    更正一下,Malament-Hogarth 时空不是单一的时空结构,事实上它是一类特殊时空结构的统称。

    它们包括:

    I. anti-de Sitter 时空

    II. Reissner-Nordström 时空 (RN 黑洞中)

    III.Kerr-Newman 时空 ( 克尔-纽曼黑洞中)

    IV.一个"卷起来"的 Minkowski 时空(补充说明,该 Malament-Hogarth 时空中的时间维被卷了起来,形成封闭类时曲线。)

    这些时空相当于是把Malament-Hogarth 时空塑造成一台时空版的无限机器。使得计算机器任意的无限枚举都可以在一个常数时间内完成。

     

    Malament-Hogarth 时空的时空结构允许超计算能力逐级递增,利用这些时空结构,

    数学家 Mark Hogarth 把 Malament-Hogarth 时空构造成一个叫 SAD -计算机 (SAD machine)的非图灵计算机,它们各部分依次能判定不可解度不同的集合。

    简要地讲,在 Malament-Hogarth 时空中进行操作,\gamma_{1} 为在无限世界线上运行的图灵机(记作 \mathrm{TM_{\infty}} ),\gamma _{2} 为观测者。

    它可以判定任何的任一如下关系形式 :

    S(z)= \exists xR\left( x,z \right) 或者 S\left( z \right) = \forall xR\left( x,z \right) ,其中 R 是递归关系。上述方式就相当于构造了一台 SAD_{1} 计算机。

    在 Malament-Hogarth 时空的操作区域为 O_{i} ,i=1,2,3,...n... ,则 :

    I. O_{i} \subset I^{-} \left( O_{i+1} \right)II. O_{i } \subset I^{-} \left( p \right)

    在 Malament-Hogarth 时空区域中重复 SAD_{1} 操作,\gamma _{1} 为一台 \mathrm{TM_{\infty}} 来判定 \forall yR(i,y) , 然后另外一台 \mathrm{TM_{\infty}} 来收集各部分结果判定 \exists x\forall yR(x,y)\gamma _{2}为观测者,收集结果。

    最终构造了 SAD_{2} 计算机。它可以判定:

    S_{2} \left( x_{3} \right) =\forall x_{}\exists yR\left( x,y \right) =\forall x_{1} \exists x_{2} R\left( x_{1} ,x_{2} ,x_{3} \right)

    或者

    S_{2}^{'}\left ( x_{3} \right )=\exists x\forall yR\left ( x,y \right )=\exists x_{1}\forall x_{2}R\left ( x_{1} ,x_{2},x_{3}\right )

     

    重复 SAD_{2} 操作,得到SAD_{3} 计算机;重复 SAD_{3} 操作,得到 SAD_{4} 计算机 ...

    最终,重复所有的操作后。可得到如下递归关系:

    S_{n+1}\left( x_{n+1} \right)=\forall x_{1} \exists x_{2}...\forall x_{n-1}\exists x_{n} R\left(x_{1} ,...,x_{n+1}\right)

    S_{n+1}^{'}\left( x_{n+1} \right)=\exists x_{1}\forall x_{2}...\exists x_{n-1} \forall x_{n}R\left(x_{1} ,...,x_{n+1}\right)

    于是,我们得到了一台 SAD_{n} 时空计算机.

    SAD_{n} 时空中:

    I. 当 n=1时,为 Malament-Hogarth 时空 ;

    II. 当 n >1 时, SAD_{n} 时空计算机由 i 台 SAD_{n-1} 计算机“串联”构成;

    III.SAD_{1} 计算机可以判定克林算数层级中的 \Sigma _{1}^{0} \cup \Pi _{1}^{0} 层级;SAD_{2} 计算机可以判定 \Sigma _{2}^{0} \cup \Pi _{2}^{0} 层级;SAD_{3} 计算机可以判定 \Sigma _{3}^{0} \cup \Pi _{3}^{0} 层级;...;而最终 SAD_{n} 计算机可以判定 \Sigma _{n }^{0} \cup \Pi _{n}^{0} 层级。

    结论:

    I. \mathbf{SAD}_{n} 可以判定 \Sigma _{n }^{0} \cup \Pi _{n}^{0}

    II. \mathbf{SAD}_{n} 可以映射至算数层级的每一层;SAD machines 可以判定完整的算数层级。

     

    最终,把所有操作全部 "串连" 在一起。相当于构造了 AD ( Arithmetical sentence deciding ) machine。

    AD machine 可以精确地求解 \aleph _{0} 函数和判定 Arithmetic 。

     

    P.S. 对 Kerr 时空进行操作步骤如图所示:

     

     

    首先,对黑洞时空世界线(位于克尔-纽曼黑洞的赤道平面的轨道)运行的图灵机 (Orbiting Machine)进行设置计算任务。

    接着,图灵机开始无穷无尽的计算任务。计算任务的计算步骤与计算时间为无限。计算机将会经历无限数量于观测者的本征时间。

    然后,观测者(操作人员)(Falling Observer)进入内视界, Malament-Hogarth event 发生,“图灵无限计算任务”这一事件在 Malament-Hogarth event 的有限时间内被观测者(操作人员)所经过。(观测者的这一路径只会用掉有限的本征时间。)

    接着,观测者穿过 Malament-Hogarth event 并从内视界离开黑洞,最终观测者离开黑洞时,图灵机的无限计算任务也已经完成。在观测者的参考系来看就相当于是图灵机在有限时间内完成了无限多次的计算步骤。

    最后,在图灵机确认完成计算任务(停机)后发送计算结果给观测者,观测者收到计算结果后,(操作人员)发出终止指令。计算完成。

     

    Malament-Hogarth 时空具体可以干些什么呢?

    答:如果 Malament-Hogarth 时空存在且计算操作可以实现,则它可以实现超级任务(Supertask)!

    超级任务(Supertask),是芝诺悖论的现代变体。指的是有限时间内完成无限多次操作序列的任务。比如说 π 的最后一位数字;汤姆逊灯;等等。

    完成该任务的机器称为 infinite machine 。

    目前主流的认识是:超级任务是不可能完成的, infinite machine 不存在。

     

    不过,在 Malament-Hogarth 时空中,在有限时间内完成无限多次操作的过程,理论上是可以完成的。

     

     

    J.芝诺机(Zeno Mchine) \clubsuit

    该模型使用\frac{1}{2^{n} }的时间来完成算法的第n步。可以在有限的时间内完成无限的运算步骤。举个例子,一种算法第一步需要0.5s,第二步需要0.25s,第三步需要0.125s,...在1秒钟之后,这段无穷步骤的算法就可以完成。

     

    另外经典图灵机的“停机问题”就可以在芝诺机上由如下的算法给出解答:

     

    begin program
      write 0 on the first position of the output tape;
      begin loop
        simulate 1 successive step of the given Turing machine on the given input;
        if the Turing machine has halted, then write 1 on the first position of the output tape and break out of loop;
      end loop
    end program
    

     

    该算法的另一种形式:

    begin 
    write 1 to the first cell of the tape (output)
     i ← 1
     while i > 0 do
        run given TM m for given input n for i steps 
             if m halts then
                write 0 to the first cell of the tape
                i ← i + 1 
             end if 
        end while
     end
    

     

    P.S.该模型同样需要可以无限分割(连续)的时间,或者保证计算机器的计算步骤可以无限的加速。可惜我们的宇宙中造不出这样的计算机器。

    虽然在量子理论的普朗克时间限制和相对论的光速限制下物理不允许这样的机器出现在现实世界。但是,在现有的理论,比如广义相对论,或许允许我们利用特殊的时空结构以另外一种方式——"计算机的无限计算步骤可以在另一个观察者有限的本征时间内完成"来达到同样的效果,即 Malament-Hogarth 时空。

     

    K.Fast-growing constructs Oracle.

    Dmytro Taranovsky 提出了一个传统非有限分析分支的有限模型,围绕一个配备一个具有以不可计算速率快速增加功能的增长函数作为谕示的图灵机,能够给出一个二阶算术的解答。

    更为具体地:如果存在一个全函数 (total function)A 对于函数 B,且对于每一个自然数 n 来说总有 B\left( n \right)\geq A\left( n \right) ,则会有一种语言 L 可由这台配有该 Oracle 的图灵机所识别,当且仅当 S 位于 L 中时该机器使用 B 作为一个谕示在输入 S 后停机。

    由于这些谓词是用某些自然有限结构的性质来解释的,因此可以说它们是有限的。

    结论:一台图灵机配 fast-growing sequence oracle 能力等价于 \Pi_{1}^{1}

    对于一个足够快速增长的序列 A,递归关系有一个通过 n 的无限下行路径(infinite descending path)当且仅当一个无限下行路径通过 n 以及然后通过一个A(max(n,m)) 的自然数 ,其中 m 是递归定义关系的长度。根据 König's lemma ,如果关系是良基(well-found)的,那么 tree 是有限的,因此机器的搜索最终会发现关系是 well-found 的。相反的,对于每台机器和输入,机器对每一个 A:ℕ→ℕ 都有一个停机计算当且仅当机器接收的答案至少和 A 给出的答案一样大。

     

    L. Active Element Machine \clubsuit

    Michael Stephen Fiske 的 Active Element Machine 由被称为 Active Element (AE)的计算基元(computational primitives)组成。

    Active Element 分为三类,分别是:输入,计算,输出。

    每个 AE 从其它 AE 接收信息;并将信息传送到其它的 AE 。现在引入对于整数(integers)集的拓展: \bar{\mathbb{Z}}=\left\{ m+kdT:m,k\in \mathbb{Z};\,dT: \mathrm{a\,\,fixed\,\, infinitesimal}\right\}

    \Gamma,\Delta,\Omega 分别是输入,计算,输出 AE 的索引集 (index set), \Gamma\cap \Omega 以及 \Omega \cap\Delta 可以为空集或非空集。

    整个机器架构定义为一个三元组: \mathscr{M}=\left( \mathscr{I,E,O}\right) ;包括一组输入 AE 。具体地:

    \mathscr{I}=\left\{ E_{i}:i\in\Gamma \right\}, \mathscr{E}=\left\{ E_{i}:i\in\Omega\right\}, \mathscr{O}=\left\{ E_{i}:i\in\Delta\right\}

    每个计算,输出 AE E_{i} 具有以下属性:

    一个 threshold \theta_{i};一个 refractory period r_{i}>0 ; 一组 pulse amplitudes : \left\{A_{ki} :k\in\Gamma \cup \Omega\right\} ; 一组 transmission times : \left\{\tau _{ki}>0:k\in \Gamma\cup \Omega \right\} ;

    时间函数 \Psi_{i}\left( t \right)=\textrm{sup}\left\{ s:s<1;g_{i}\left( s \right) =1\right\} 表示上次触发 AE E_{i} 的时间; g_{i}\left( s \right) 是 AE E_{i} 的输出函数;

    一个二进制输出函数 g_{i}\left( t \right) 用来确定 E_{i} 是否会在时间 t 被触发,则:

    {\displaystyle g_{i}\left( t \right)={\begin{cases}1,&{\text{if }}\,\sum_{}^{}{A_{ki}\left( t \right)>\theta_{i},t\geq \Psi _{i}\left( t \right)+r_{i}}{\text{ holds}};\\0, &{\text{}}t<\Psi _{i}\left( t \right)+r_{i}\end{cases}}}

    定义 W_{ki}\left( t \right)=\left\{ s:\textrm{active element}\, E_{i}\,\textrm{fired at time}\,s\,\textrm{and}\,0\leq t-s-\tau_{ki}<\omega _{ki}\right\}

    W_{ki}\left( t \right) 中的元素个数以 \left| W_{ki}\left( t \right) \right| 表示,若 W_{ki}\left( t \right)=\emptyset\left| W_{ki}\left( t \right) \right|=0

    一组输入函数 \left\{ \phi_{ki}:k\in\Gamma \cup Q \right\} ,输入函数值的计算方式为: \phi_{ki}\left( t \right)=\left| W_{ki} \left( t \right)\right|A_{ki}\left( t\right)

    pulse widths,refractory period,transmission times 为正整数;pulse amplitudes 和 thresholds 为整数;代表这些函数参数的时间 t 为 \bar{\mathbb{Z}} 的一个元素。

    由于 AEM 能够在执行其程序时更改其体系结构,并且使用来自环境中的随机比特,AEM 可以表示 \left[ 0,1 \right] 中的任意一个实数。

    任意一类语言 L 且 L\subseteq\left\{ 0,1 \right\}^{\ast} 都可以被 AEM 所识别。

     

    M. Self-similar cellular automata \clubsuit

    设想在一个特殊的宇宙中,该宇宙支持着时空的无限可分性。

    目前,“时空可无限分割”这一假设属性已经被用于探讨超越图灵计算的提议,比如 Zeno Machine;这个模型是基于图灵机模型拓展而来。那么,有一个问题是:基于“时空的无限可分性”这一属性,其他的可计算模型是否可以拥有超越图灵机的计算能力呢?

    答案是肯定的。

    Martin Schaller 和 K. Svozil 给出了基于这一属性的元胞自动机(cellular automata)的构架。

    普通元胞自动机的基本结构是由胞体在空间和时间的均匀镶嵌所决定的。如下图所示:

    元胞自动机的演化图示

    而对于 Self-similar cellular automata 作为一个自动机:无限多个胞体在一维晶格上运行。同一胞体的每两次更新之间的大小和时间根据其在晶格中的位置而变化。

    对于每个胞体 j ,大小为: \frac{1}{2^{j}} ;两次更新之间的时间与胞体大小成正比。

    同时自动机所在的晶格是嵌入至整个 \mathbb{R} 中:对于起始胞体 j 来说 j\mapsto 2-\frac{1}{2^{j-1}} ;这样整个晶格被映射至 \left( -\infty,2 \right) ;而胞体 0 占据区间 [0,1) 。整个机器如下图所示:

     

    一个 Self-similar cellular automata 的演化;横为时间,纵为 cells

    接下来:

    一个 Self-similar cellular automata 是一个三元组 : \mathscr{A}=\left( S,f_{c},f_{d} \right) ;S 为有限状态集;后两项为特定规则 (local rule)。每个胞体都有状态集中的一个状态,cell j 会在时间 \frac{k}{2^{j}} 更新自己的状态(k 为一个整数)。在任何给定的时间,自动机的的配置是一个映射 c:\mathbb{Z}\rightarrow S 它指定所有细胞的状态。另外,cell j 会在时间 \frac{2k}{2^{j}}=\frac{k}{2^{j-1}} 与自己的左邻 cell 同时进行再次转换。这种转换称为 coupled ,一个胞体进行 coupled 时颜色为灰色。

     

    下面利用该自动机来构造一个可以进行超计算的机器。

    对于一台任意图灵机 M,这台自动机利用一个静态构成的 \mathscr{A}_{M}=\left(S,f_{c},f_{d}, \square \right) 来模拟 M。

    一个集合 : T=\left( Q\times \left\{ \triangleleft ,\triangleright \right\} \right)\cup\Gamma ;而自动机的状态集 S 为: S=T\cup\left( T\times\left\{ \blacktriangleright \right\} \right)\cup\left\{ \square , \blacksquare ,\diamond \right\} 。位于状态集 Q 内的 q,使用 q^{\triangleleft } 表示 \left( q,\triangleleft \right) ; q^{\triangleright } 表示 \left( q, \triangleright \right)

    \mathscr{A}_{M} 的 local rules 由 block transformations 指定, x_{\blacktriangleright } 表示位于 T\times\left\{ \blacktriangleright \right\} 中的一个元素 \left( x, \blacktriangleright \right) ; x\in T;a,b\in\Gamma;q,p\in Q

    定义机器的 block transformations :

    \begin{matrix} \blacksquare x \mapsto\blacksquare x_{\blacktriangleright }\, \textrm{if}\,x\neq q^{\triangleleft } \,&x\square \mapsto\diamond x \, \textrm{if}\, x \neq q^{\triangleright }\\ x_{\blacktriangleright} \diamond \mapsto\diamond x\,&q^{\triangleright } \square \mapsto q^{\triangleright }B_{\blacktriangleright } \\ a\,b \mapsto a\,b_{\blacktriangleright} & B_{\blacktriangleright }\square\mapsto \diamond B\\ q^{\triangleleft }a \mapsto q^{\triangleleft }a_{\blacktriangleright } & \blacksquare \diamond \mapsto \diamond \blacksquare \\ a\,q^{\triangleright } \mapsto a\,q_{\blacktriangleright }^{\triangleright } & \end{matrix}

    接下来:

    \mathscr{A}_{M} 使用配置 \blacksquare q_{0}^{\triangleright }\diamond a_{1}\diamond a_{2}...\diamond a_{n}\diamond 来模拟在输入 a_{1}a_{2}...a_{n} 上运行的图灵机。 Q\times\left\{ \triangleleft ,\triangleright \right\} 中的一个符号充当图灵机的读写头的作用,面向左 \triangleleft 或右 \triangleright ,从而指示接下来扫描左侧还是右侧的操作带上的符号。通过每个带上符号和读写头两个状态 xx_{\blacktriangleright } 的 stop-and-go 同步形式实现可控转换。转换由左分隔符 \blacksquare 开始;如果与符号 x 相邻则 block transformations 中的 \blacksquare x \mapsto\blacksquare x_{\blacktriangleright }\, \textrm{if}\,x\neq q^{\triangleleft } \, 会将 x 转换为 x_{\blacktriangleright } 并且它向右移动一格变回 x 并与 \diamond 交换位置。如果 x,y\in T 且两个符号相邻,则右边符号被触发为状态 y_{\blacktriangleright } 。如果它们其中一个位于带上;另一个作为图灵机读写头的作用,则自动机利用余下的 block transformations:

    \begin{matrix} \mathrm{If}\,\delta (q,a)=(p,b,R) & \mathrm{If}\,\delta (q,a)=(p,b,L) \\ q^{\triangleright }a\mapsto bp_{\blacktriangleright }^{\triangleright } & q^{\triangleright }a\mapsto p^{\triangleleft }b_{\blacktriangleright}\\ aq^{\triangleleft }\mapsto bp_{\blacktriangleright }^{\triangleright } & aq^{\triangleleft }\mapsto p^{\triangleleft }b_{\blacktriangleright } \end{matrix}

    来模拟在图灵机上的一个计算步骤。

    最终结论: \mathscr{A}_{M} 停机时间会在少于 4 个时间单位当且仅当图灵机 M 在输入 w 上停机;如果 M 不停机则 \mathscr{A}_{M} 会在 4 个时间单位时进入配置 \diamond ^{\infty}

     

    N.极限递归 \clubsuit

    由 Gold 提出的极限递归理论中图灵停机问题可以在一个有限时间里得到判定结果,不过我们不能知道这个结果在确切何时取得,于是大部分学者认为在无限长时间后才能取得结果。

    更具体地:如果一个函数 P 是一个极限递归谓词,则满足一个广义递归函数 f 对于每一个 (x_{1},...,x_{n}) 当且仅当

    P\left( x_{1} ,...,x_{n}\right)\Longleftrightarrow \lim_{y \rightarrow \infty}{f\left( x_{1} ,...,x_{n},y\right)}=1

    \neg P\left( x_{1} ,...,x_{n}\right)\Longleftrightarrow \lim_{y \rightarrow \infty}{f\left( x_{1} ,...,x_{n},y\right)}=0

    其中:

    \lim_{y \rightarrow \infty}{f\left( x_{1},...,x_{n} ,y\right)}=k\overset{\underset{\mathrm{def}}{}}{=}\exists y \forall z\left( z\geq y \rightarrow f\left( x_{1},...,x_{n} ,z\right)=k\right)

    而极限递归谓词 P 位于 \Delta_{2}^{0}

     

    O.波计算机

    在物理学家费曼的演讲《The Character of Physical Law》中提及,对于物理现象的计算机仿真时,即使做了全面离散化也不保证仿真的有效性,从而所谓有限自然假说的初衷无法满足。在实数域上可以存在无限多不可计算的连续函数,并且求导和积分不保持可计算性。那么描述某个物理体系的微分方程完全可以有一个不可计算的解,不满足“总能用有限步运算逼近到充分的精度”的条件。上世纪80年代,文献 Advances in mathematics 39,215-239(1981)中:机械波的存在遵循着三维波动方程(wave equation):

    \frac{\partial^2 u}{d x^{2}}+\frac{\partial^2 u}{\partial y^2}+\frac{\partial^2u }{\partial z^2}-\frac{\partial^2u }{\partial t^2}=0

    而为了使该波动方程具有唯一的解,这个唯一解 u 将由两个初始条件(initial conditions)所决定:

    当 t = 0 时 : \frac{\partial u}{\partial t}\left( x,y,z,0 \right)=0u\left( x,y,z,0 \right)

    而初始条件可由一个图灵可计算函数 f 所对应: u\left( x,y,z,0 \right)=f\left( x,y,z \right)

    但在 t 时刻后,f 在波动方程中的解 u\left( x,y,z,t \right) 不可计算,且该解的数值 u\left( 0,0,0,1 \right) 是一个不可计算的实数。

    即:可以用机械波构造出了初始条件可计算,但解一般不可计算的一个范例。曾被提议制造利用机械波为计算介质进行超计算的波计算机。

     

    Q.超递归算法(Super-recursive algorithm). \clubsuit

    由 Mark Burgin 提出,并在此基础上提出好几种新的计算模型(例如Gold提出的极限递归就是其中之一。)。他的论述依赖于对算法更广泛的定义, 这种定义上的扩展使得一些归纳性图灵机包含的不可计算函数变得可计算。并且 Mark Burgin 相信他的超递归算法理论可用于反证丘奇-图灵论题。不过这种对邱奇-图灵论题的解读与计算机科学的常规解读不同,把超递归算法归于邱奇-图灵意义上的算法的这种看法并未受到计算领域的广泛接受。

    Mark Burgin 的归纳图灵机 (inductive Turing Machine)与经典图灵机类似,与之不同的是在于它们决定输出的方式(即:,计算的结果)。在它的操作过程中,一个归纳机器在连续的方格上打印符号,这些符号构成了计算结果的符号序列。有时,如果机器进入了它的停机状态,它就会停止运转,就像一台普通图灵机一样。然而,有些情况下,机器实际上并没有停止,但这并不能阻止机器给出结果。

    所以:对于任意图灵机 \mathscr{T} ,有一个归纳图灵机 \mathscr{M}\mathscr{M} 可以计算与 \mathscr{T} 相同的函数。

    归纳图灵机有三个部件组成: hardware, software, infware. 接受的语言是一个三元组 \left( L_{i} ,L_{w},L_{o}\right)L_{i} \ne L_{w}\ne L_{o} \ne L_{i}

    特别地, \mathscr{M} 是一个归纳图灵机,它包含一个通用图灵机 \mathscr{U} 作为子程序。给定一个图灵机 \mathscr{T} 的字符串 u 和一个 description D\left( \mathscr{T} \right)\mathscr{M} 使用 \mathscr{U} 来模拟输入 u 运行的 \mathscr{T} 。在操作过程中, \mathscr{M} 在输出磁带上写入一个 0 。如果 \mathscr{U} 停机,意味着 \mathscr{T} 在输入 u 上停机: \mathscr{M} 写入1。现在 \mathscr{M} 的计算结果等于 1 如果 \mathscr{T} 停机,否则等于0。

    更重要的是:一个关系 Y\in \Pi_{n}^{0}\cup \Sigma_{n}^{0} 都存在一个 n 阶归纳图灵机使得可以判定 Y 。

     

    R.量子引力计算机

    著名的数学物理学家罗杰·彭罗斯 ( Roger Penrose ) 走出了更加大胆的一步,他推测量子引力不可能用普通计算机或者量子计算机来模拟,即使有可以任你处置的无限的时间和内存。彭罗斯认为应把模拟量子引力的问题归入逻辑学家阿兰.图灵( Alan Turing )和库尔特·科德尔( Kurt Godel )在1930年代所研究的一类问题中,这些问题里有的比 NP 完全问题还要难解--比如确定一个给定的计算机程序是否会停止运行的问题( 比如说“停机问题” )。

    最新的量子引力学的进展好像支持一个相反的结论,即它们暗示一台标准的量子计算机甚至可以模拟量子引力过程,比如黑洞的形成与消失。最值得一提的是源自弦理论的 Ads/CFT 对偶 ,它断定了两种看起来极为不同的理论之间的“对偶性”。对偶的一边是反德西特空间( Anti de Sitter )理论:它是关于一个假想宇宙的一个理论,这个假想宇宙有一个负的宇宙常数,它导致整个宇宙被一个反射边界所包围。而另一边则是共场理论( Conformal Field Theory ):一个没有引力,只存在于 AdS 空间的边界上的“普通”量子场理论。Ads/CFT 对偶原理已有压倒性的(虽非确凿的)证据指出,任何关于在 AdS 空间中是什么情况的问题都可以转化为关于 CFT 的一个“相当的”问题,反之亦然。

    这就意味着,如果我们想在AdS空间中模拟量子引力现象,我们就可能可以先把这个问题转化到CFT 那一边,然后在量子计算机中模拟这个 CFT ,最后再将结果转化回 AdS 中。这其中最关键的一点是,因为 CFT 不包括引力,在量子计算机中模拟它的难度就“仅仅”是相对简单的如何在量子计算机中模拟量子场论的问题。更广义地说,我们能从 AdS/CFT 中所了解到的是,即便量子引力论看起来“疯狂”--即使它包括了非定域性、虫洞及其他的新奇事物--它也可能有一个更加“驯服”的与之对偶的叙述方式。(要让这成为可能, AdS 与 CFT 描述之间的转化需要在计算上是高效的--也有可能有些情形下它没办法高效。)

     

    S. Coupled Turing Machines \clubsuit

    该模型也由 Copeland 和 Sylvan 提出。这是在计算过程中拥有一个或多个输入通道来提供输入的计算模型。这一输入可以以机器的字母表中的一个符号的形式写在机器的操作带的第一个方格上。这个方格是为特殊的输入而保留,不能由读写头写入。与谕示机一样, 特定的输入序列决定了 Coupled Turing Machines 可以执行的功能。例如,如果模型有一个又一个的 \tau 位输入,则该模型可以计算所有其他的递归可枚举函数。

    具体地:设一个数 u\in\mathbb{R} 是一个位于 \left\{ 0,1 \right\} 之间的一个不可计算实数,且形式为: 0.a_{1}a_{2}a_{3}...

    Coupled Turing Machine 的输入通道在 T 的操作带的一个方格上写入符号,输入数据流中的第一个符号是 a_{1} ,第二个符号是 a_{2} ,依此类推。当每一个符号被写入时,CTM 可以执行一些微不足道的计算,例如:乘以2;并将结果写在操作带的某些指定的方格上。

    所以:一个 CTM 可以计算出比通用图灵机更多的东西。

    P.S 被换下来的 Asynchronous Networks [1] 和 Error Prone [2] 模型可查阅:

    [1] Copeland and Sylvan , Beyond the universal Turing machine. Australasian Journal of Philosophy 77, 1 (1999), 44–66.
    [2] Toby Ord , Hypercomputation:computing more than the Turing barrier
    available version

     

     

    在计算理论历史上,也有人提出过量子版本的 hypercomputation 模型。

     

    T.量子模型. \clubsuit

     

    1990年,Norton 探讨了 Supertask 在量子领域实现的可能性。他考虑了一个具有无限晶格点阵(Infinite lattice)的交互谐振子(Harmonic oscillators)系统。如下图所示:

     

     

    Norton 假设每两个谐振子之间的 spring 都具有相同张力以及相同的系统运动方程解,Norton 发现它可以自发地在有限的时间内产生无限连续的振荡。利用这个系统作为模型, Norton 制造了一个类似 Supertask 的谐振子量子晶格点阵。

    以一个无限晶格点阵的 2 维量子系统作起始,其每一个谐振子都具有一个基态 |\phi \rangle 和一个激发态 |\chi \rangle 。考虑粒子们的 basis vectors, 其向量集 (Collection of vectors):

    |0\rangle= |\phi\rangle\otimes|\phi\rangle\otimes|\phi\rangle\otimes|\phi\rangle\otimes...

    |1\rangle= |\chi\rangle\otimes|\phi\rangle\otimes|\phi\rangle\otimes|\phi\rangle\otimes...

    |2\rangle= |\phi\rangle\otimes|\chi\rangle\otimes|\phi\rangle\otimes|\phi\rangle\otimes...

    |3\rangle= |\phi\rangle\otimes|\phi\rangle\otimes|\chi\rangle\otimes|\phi\rangle\otimes...

    |4\rangle= |\phi\rangle\otimes|\phi\rangle\otimes|\phi\rangle\otimes|\chi\rangle\otimes...

    ......

    之后 Norton 得到了这交互系统薛定谔方程的微分形式:

    i\frac{dC_{0}}{dt}=0 ,...,\,\,\,i\frac{dC_{n}}{dt}=C_{n}+ia\left( C_{n-1}-C_{n+1} \right),...

    Norton 争辩说, 他的解决方案中在无限晶格中的所有节点开始由基态转变为激发态的时间是有限的。

    Norton 的量子 Supertask 需要一个非标准(Non-standard)的量子系统,因为他所提出的动力学演化不是幺正(unitary)的, 即使它服从一个微分方程形式的薛定谔方程的波函数空间中。

     

    U. 量子模型二. \clubsuit

    如果我们不断地监控一个量子系统, 比如一个不稳定的原子, 会发生什么?预测的效果是系统不会改变, 即使它是一个不稳定的原子,也会迅速衰变。

    1977年,Misra 和 Sudarshan 提出对一个芝诺式 supertask 的系统进行“精确监测”。假设一个不稳定的原子是根据某种幺正演化定律(law of unitary evolution ) U_{t} 而演化的。假设我们衡量的原子是否已经发生衰变是遵循芝诺二分法的回归形式。即我们在时间 t 进行测量;而后在时间 \frac{t}{2} 进行测量;接着在时间 \frac{t}{4} 进行测量,等等。让 E 为粒子初始未衰变状态的射影(projection)。在 supertask 的每个阶段找到原子未衰变阶段然后对应于每个序列:

    EU_{\frac{t}{2^{n}}}E,\left (n \geq 0 \right )

    Misra 和 Sudarshan 使用此序列作为一种模型进行连续测量,假设上面的序列收敛于一个算子: T\left ( t \right )=E 而这样做的所有时间大于或等于零。然后在固定时间 t=0 对原子进行连续观测。他们从这个假设证明, 对于大多数合理的量子系统, 如果初始状态在 \textrm{Tr}\left ( \rho E \right )=1 的意义上是未衰变的,那么原子在任意给定时间间隔 \left [ 0,1 \right ] 中衰变的概率等于零。也就是说, 持续的监测意味着原子不会衰变。

    同时意味着,如果我们可以连续地测量一个不稳定原子以观察它是否仍然处于初始状态,则始终能发现该原子处于初始状态。

    这个提议引发了大量的反响。Ghirardi 等人和 Pati 反对这样的芝诺式量子测量模型,因为它与量子理论的其他特征,如时间-能量不确定关系(time-energy uncertainty relations)相抵触。不过 Bokulish 认为,这种 Supertask 仍然可以进行:当满足对系统的测量(measurement )与系统的幺正演化(unitary evolution)相交换且 E 为其能量本征态的投影(projection)。

     

    V. Hypertask 模型 \clubsuit

    Miha Habič 对原有的 Hamkins 无限时间图灵机进行拓展,得到了一个新的计算模型并在计算能力上与原有的无限时间图灵机进行比较。

    与无限时间图灵机不同的是 Miha 模型会使用一个 “基数状态”(cardinal state)取代了“极限状态”。并且机器在 \kappa 阶段 (stage \kappa )时允许 \kappa 是一个不可数的无穷基数并执行以下操作:机器读写头位于第一个方格上;机器位于基数状态,操作带每一个方格的数值为前一个方格数值的极限上界 (lim sup)。

    定义机器的可计算函数都位于 Cantor space 2^{\omega} 上。接下来:

    该机器可判定无限时间图灵机的停机问题。

    ITTM 的停机问题: 0^{\blacktriangledown }=\left\{ \left( p,x \right);\varphi_{p} \left( x \right)\downarrow\right\}

    一个 stabilization problem : S=\left\{ \left( p,x \right); \mathrm{the\,\,output\,\,of\,\,}\varphi_{p}\left( x \right)\mathrm{stabilizes}\right\}

    0^{\blacktriangledown } 可简化为 S 的可判定性:给定一个程序 p 和一个输入 x ,同时构造一个类似与 p 的新程序 p' 可在完成 p 的各项指令后定义一个特定单元方格格式(称作 flag);程序 p 会在 x 上停机当且仅当 p' 在 x 上稳定。

    同时 S 也是可判定的,考虑一个算法:一对 \left( p,x \right) 它会模拟 \varphi_{p}\left( x \right) 和每次模拟输出变化的特定单元格格式。当到达一个基数状态时,如果 flag 显示为 1,则输出 “No”,显示为 0 则输出 “Yes”。这个算法可判定 S。

    接下来:

    机器的可计算函数都会在时间 \aleph_{\omega_{1}} 内停机,也就是说,在它的计算任务内至多可以执行的计算步骤总数为 \aleph_{\omega_{1}}。这是一个相当大的不可数基数了。

    在一个有限任务序列中可以执行不可数无穷数量的操作步骤,则称它为超任务 (Hypertask)。如果是可数无穷,为超级任务(Supertask)。

     

    不过即使把计算任务步骤拓展到不可数无穷,虽然模型计算能力得到了提升,但并不显著。

    结论:该模型与配了 0^{\blacktriangledown } 谕示的无限时间图灵机在能力上是等价的。

    想象一下给无限时间图灵机配一个跳跃算子(jump-operator)黑箱:它可以把一个实数写在一个特殊带上,然后一个 x^{\bigtriangledown } jump 出现在另一条特殊带上。

    这种情况下可看做配了 0^{\blacktriangledown } 的无限时间谕示机。然而,它的计算能力仍然位于 \Delta_{2}^{1} 内。

     

    W. 快子模型 \clubsuit

    在相对论中,一个基本事实是: E^{2}-p^{2}=m^{2}

    E 是一个物体的能量, p 是它的动量, m 是它的静质量,我们就称之为“质量”。其中光速 c=1

    具有质量的普通物质,处于光锥之内,速度小于光速;

    E^{2}=p^{2} :零质量物质,存在光锥之上,速度等于光速;

    但理论上还存在另外一种情况,速度大于光速的物质:快子(tachyon)。

    单个快子的波函数满足描述自旋零粒子的一般方程即 Klein-Gordon quation: \left( \square +m^{2}\right)\varphi=0 .

    其中 \square 是达朗伯算符 (d'Alembertian),其 3+1 维形式为:

    \square=\frac{\partial^{2}}{\partial t^{2}}-\frac{\partial^{2}}{\partial x^{2}}-\frac{\partial^{2}}{\partial y^{2}}-\frac{\partial^{2}}{\partial z^{2}}

    不同之处在于快子的 m^{2} 是负的,所以质量为虚数。

    虽然目前在实验上还没有观测到快子态, 但是相对论在理论上给出了其存在的可能性。

     

    Takaaki Musha 探讨了基于快子的计算模型是否会拥有超越图灵机的能力。

    首先,Feynmann 定义了计算过程中每一步所需的能量为:

    per \,\,step=2k_{B}T\frac{f-b}{f+b} 其中 k_{B} 为玻尔兹曼常数,T 为温度,f 为计算正向速率,b为逆向速率。假设在计算过程中没有能量供应以及参数 f 和 b 是固定的,则无限次计算步骤可表示为:

    E_{1}=kE_{0},...,E_{n+1}=kE_{n},... 其中 E_{0}=k_{B}{T},k=\frac{2(f-b)}{f+b}

    E_{n} 为第 n 步计算的能量。从上面得到 E_{n}=k^{n}E_{0} ,然后每一个计算步骤的能量损失为: \Delta E_{n}=E_{n-1}-E_{n}=\left( 1-k \right)k^{n-1}E_{0} 其中 n\geq1

    而一个平均能量为 \Delta E 的量子系统演化出一个正交态(orthogonal state)的时间 \Delta t 至少为 :

    \Delta t=\frac{\pi \hbar}{2\Delta E} , 设置 E=\Delta E_{i} , 则无限计算步骤的总能量就等于 E_{0}

    这样无限计算步骤所需要的总时间为:

    T=\sum_{i=1}^{\infty}{\Delta t_{n}}=\frac{\pi \hbar}{2E_{0}}\sum_{i=1}^{\infty}{\frac{1}{\left( 1-k \right)k^{n-1}}}

    不过如果仅仅是这样的话,上式在满足 0<k<1 时,无限步骤计算需要无限的时间。

    现在引入快子。

    相对论关系对于快子也是有效的,即使是一个虚质量 i \cdot\,m_{0} ; 于是得到了新形式: E=\frac{m_{0}c^{2}}{\sqrt{\left( \frac{v}{c} \right)^{2}-1}}\,\,\,\,\,\,p=\frac{m_{0}v}{\sqrt{\left( \frac{v}{c} \right)^{2}-1}}

    然而不确定性关系对于快子也是有效的,定义新的时间-能量不确定性关系:

    \Delta E\Delta t\approx \frac{\hbar}{\frac{v}{c}\left( \frac{v}{c}-1 \right)}

    快子的量子计算系统所需要的总时间就变成了:

    T=\frac{\pi \hbar}{2E_{0}}\sum_{i=1}^{\infty}{\frac{1}{\beta_{n}\left( \beta_{n}-1 \right)\left( 1-k \right)k^{n-1}}} 其中 \beta_{n}=\sqrt{1+\frac{m_{0}^{2}c^{4}}{2^{kn}E_{0}^{2}}}

    结论:T 在满足 0<k<1 时将会收敛于某个有限值。这意味着无限的计算步骤可以

    使用快子在有限的时间内完成。

     

    物理学家 Deutsch 所设想的 “终极超计算模型” ,即存在一台可以仿真所有其他物理系统的通用仿真机 。这是一个未定的假说:CTD原理 (Church–Turing–Deutsch principle )。如果该论题为真,那么计算机的计算能力一定是存在上限的,虽然说上限不一定是图灵机。

     

    除此之外,超计算模型还有很多很多,例如概率图灵机,无限状态图灵机,等等等等。这里不再一一列举了。

    P.S. 这里的的超计算模型介绍是不太严谨的,如有错误,请多包涵。仅仅是高度科普高度口水化的介绍。

     

    不过,对于任何一台谕示机,无论所带谕示的谕示能力多么强大,都存在其自身谕示不能判定,必须由更高一阶的谕示机才能判定的停机问题。通过添加能力越来越强的“谕示”来让经典图灵机不断突破计算能力限制,而谕示机的停机问题的层级为原先谕示机的层级的图灵跳跃(Turing jump),是一种顺序关系,于是得到一个0^{\left( n \right) } n为超穷序数的超穷层级,称为图灵度层级(不可解度)

    经典图灵机可以计算的可判定问题位于最最底层,是最最简单的层级,记作0。

    除了0以外的全部层级都是不可计算的不可判定问题。而且层级越高,问题越难。

     

    另外,在一个关于自然数的逻辑公式 P(x) 中,只有一个自由变元 x ,那么,使这个公式成立的所有值组成的集合为 P(x) 定义的自然数集。在这其中没有量词的命题被称为零阶命题,而有量词的命题,它们开头必定由存在量词和全称量词交错组成,这样交错的段数,就是命题的阶数。对于一个 n 阶命题,如果它的开头是存在量词,我们就称它为 n 阶存在命题,反之则是 n 阶全称命题。

    在这些这些类别的命题能定义的自然数集中,0阶命题定义的自然数集组成的集合称为 \Delta _{0}^{0},而将 n 阶存在命题和 n 阶全称命题定义的自然数集组成的集合分别称为 \Sigma _{n}^{0}\Pi _{n}^{0},这些集合组成了一个向上无限绵延的层级,每一层都是自然数集组成的集合,阶数越高,命题能定义的自然数集也越多,表达能力也越强。这就是除了图灵度以外可以判定一个计算机器计算能力的另一个层级:克林算术层级(Kleene arithmetical hierarchy)

    在算术层级中:

    \Sigma_{n}^{0}=\exists x_{1}\forall x_{2}...\exists x_{n}R\left( x_{1}...x_{n} \right)\Pi_{n}^{0}=\forall x_{1}\exists x_{2}...\forall x_{n}R\left( x_{1}...x_{n} \right) 其中 \Delta_{n}^{0}=\Sigma_{n}^{0}\cap \Pi_{n}^{0}

    一个关系 R\in \Pi_{n}^{0}\bar{R}\in \Sigma_{n}^{0} ;

    一个关系 R\in \Sigma_{n+1}^{0} 则满足在 \Sigma_{n}^{0} 中是递归可枚举的。

     

    至于基于超算模型的计算机能否在我们的宇宙中制造,也就是超计算的物理实现可能性,我们目前无法得知,因为:

    I. "丘奇-图灵" 论题 (Church-Turing thesis)

    首先是弱化的论题版本:想象一个理想化的人类,不限制时间和内存资源(纸和笔),图灵曾描述实施的那种理想化的计算——即根据某些类型的正式规则使用纸笔计算并声称:任何这样的算法,在原则上可以由这样一个理想化的人类代理来执行,实际上是通过一个合适的图灵机程序进行的。

    大多数学者说到 Church-Turing thesis 时会想到的弱化的版本。目前至少这弱形式的Church-Turing 包括数学上的各种正式的可计算模型:包括图灵机;修改和扩展的图灵机:如 multi-tape 图灵机等等,但也包括基于理想化版本的基本编程语言的机器比如说 C++ 或者其他的计算机语言。所有这些形式的可计算性的概念都被证明是等价的——它们都可以相互模拟——这使我们认为我们已经正确地捕获了一个关于可计算能力的概念。它相对来说没有太大争议。

    然而还存在着强化版本:强"丘奇-图灵论题 "。它断言不仅是所有理想化的纸笔计算程序和算法程序都可由图灵机模拟,原则上在我们的物质世界的计算,包括物理系统都可由图灵机模拟。

    我们并不知道这个论题是否真正地对我们所处的宇宙的计算能力造成制约。如果论题为真;那么是否可在我们的宇宙构造 hypercomputation 的答案就是否定的。

    就目前来说,我们能实际运用的计算模型都严格等价于经典图灵机。

     

    II. 目前物理上的限制.

    • 量子物理框架下的布莱梅曼极限(Bremermann's limit);
    • 贝肯斯坦界限(Bekenstein Bound):量子物理框架下一个质量为 m 半径为 R 的球体所能储存的最多信息量为 I 则 {\displaystyle I\leq {\frac {2\pi cRm}{\hbar \ln 2}}} ;该上限使得真正处理实数的计算机(如 Blum–Shub–Smale machine 和 Real computer)不可实现,即便是在没有热噪声的假想环境里也不例外。
    • 热力学极限,再加上大脑中的各种电信号,环境中的噪音,使得无限神经网络不可实现。
    • 数学对象并不一定总可以在物理上找到对应。目前在所有的 Hypercomputation 模型中绝大部分都只是只能在数学上成立的"数学机器",在物理上是无法实现的。
    • 几乎所有的候选量子引力(quantum gravity)模型都希望时空是离散的,这是个很大的麻烦。

     

    III. 潜在的物理模型及障碍.

    不过并不是所有的超计算模型都只能在数学上存在,已经有部分模型在物理上找到了对应对象。

    它们的实现在物理上是可能的。

    不过这些模型学术界对它们是否能真正地在物理上突破图灵屏障至今存在质疑和争议。比如说:

    SAD machine:

    • 它所需要的 Malament-Hogarth 时空只是单纯在广义相对论框架下得出的结果,并未考虑量子引力。因此我们不知道量子引力是否会对时空结构本身造成破坏。
    • 计算机中的热噪音,Malament-Hogarth 时空的蓝移问题会导致其噪音被放大而掩盖通讯信号。而计算机为抵抗噪音造成的耗散不可避免,这将导致计算机需要无限大的能量维持运作,这是非常不现实的。因此要让 Malament-Hogarth 时空的超计算确实可行,计算机中就不能存在热噪音。
    • 霍金辐射. 这也是我为什么不希望霍金辐射真正存在的根本原因。存在霍金辐射的黑洞会最终导致黑洞蒸发消失。而从黑洞形成到消失的时间为: {\displaystyle t_{\mathrm {} }={\frac {5120\pi G^{2}M_{0}^{3}}{\hbar c^{4}}}} 。这会导致计算机的无限计算还没完成黑洞就消失了。因此超级任务无法完成。

    封闭类时曲线计算:

    • 封闭类时曲线计算机所需要的可以进行时间旅行的类时闭曲线时空的特殊时空结构在数学上是可能的。但如果在正能量条件普世的条件下现实的物理系统就不允许它的出现和存在。除非自然规律允许负能量的物质出现。
    • 封闭类时曲线可以明确的计算能力的问题判定范围是全部 PSPACE 。即使用一个 Polynomial - size 字符串,封闭类时曲线计算机可以在多项式时间内准确判定全部PSPACE。但进一步放宽条件可得到一个新的计算能力范围 \mathrm{Computable_{CTC}} ,可以证明 \mathrm{Computable_{CTC}} =\Delta_{2}^{0} 。不过这不代表它真的就"一定可以解决" 。因为这需要任意长度字符串的计算在封闭类时曲线中得到允许 (这代表需要无限宽的输入通道)才有可能真正做到。
    • 面对这类不可计算问题时,计算机所拥有的符合自治性结果将不再唯一;面对自治性结果不唯一的情况时,大自然将会让封闭类时曲线计算机从所有的自治性结果中选择令整体冯·诺依曼熵最大的结果。不过这是一个坏消息,因为直觉上计算机的电路板被烧穿,整个机器崩溃会带来更高的冯·诺依曼熵。当计算机对"机器崩溃,直接坏掉。"和"吐出该问题的判定结果。"的选择可能性时,封闭类时曲 线计算机更有可能会选择前者......

    机械波计算:

    • 波计算机所利用的不可计算机械波,即通过构造了一个可计算函数,其导数是非递归不可计算函数。再对其结果进行扩展,构造出一组特殊的偏微分方程,在某个特定的初始值下,某个时刻 t 后的解不可计算。 但该偏微分方程组可作为某个物理系统的演化函数。 这个系统理论上可以以机械波进行对应。当然,这个系统是否可以利用人为实验构造出来就另当别论了。

     

    IV.如果宇宙不是一台图灵机。

    • 非常感谢

      @锥管

      的回答。他给出了永远不会因霍金辐射的影响而蒸发的黑洞质量下限: M_0\ge\frac{c^6}{16\pi \sigma G^2 T_0^4 t_0}\approx3.5\times 10^{27}M_{\odot}

    这个超大质量黑洞由于不再受到霍金辐射的影响(即使它是真实的物理现象),所以在计算机无限计算中因为黑洞不会消失而不影响计算。因此利用它构造 hypercomputer 是可能的。

    • 正如费曼在他的演讲中所表达的困惑,一个描述某个物理体系的微分方程完全可以有一个不可计算的解,不满足“总能用有限步运算逼近到充分的精度”的条件。换言之,有效的数值解都不会存在(更不用说解析解了)。

    引用恩里科 · 费米的一句话:

    圣经中并没有说过一切大自然的定律都可以用线性方程来表示。

    同理没有解析解的非线性方程,数值近似是有力的武器——但是那同时也就不知不觉假设了算法可解性,一个同样是“圣经里”没有的假设。

    用于构造不可计算机械波的方式,说明理论上我们可以通过构造出一个物理系统,让其演化出的物理系统可以计算一个图灵不可计算函数。 理论上超越图灵机的函数在物理上是可以存在的。

    是否可以说,存在着一部分物理体系,它们无法用图灵机的有限步运算步骤进行模拟和重现,即不可计算的物理现象。也就是说,物理定律不是图灵可计算的。

    • 另外,如果我们的万物理论(Theory of everything)是基于弦理论的 M-theory 的话,会有一个不可思议的结果:M-theory 具有 T-对偶性(T-duality):采用弦论把一个维度包进一个半径为 R 的圆圈中,在采用另外一个弦论把一个维度包进一个半径为 1/R 的圆圈中,两者对比是完全等价的。

    即使让 R 变得非常小,甚至小于普朗克长度,也成立。因为在普朗克尺度时空会呈现出泡沫状,而远大于和远小于普朗克尺度的时空则会是平滑的,二者完全一致。如果它最终是正确的,也就意味着,小于普朗克距离和大于的所遵循的物理学相等。弦论最小的普朗克距离以内,也可以有一个完整的宇宙。同理,我们也可以利用场论而非数字化结构来描述整个宇宙。从这点看,宇宙也不是一台图灵机,物理系统也不是一个计算机程序。

    • Pour-EI 等人除了构造不可计算的波动方程之外,还证明了在可分希尔伯特空间中(很重要,用于模拟物理现象):

    存在一个有效的确定有界自伴算子(determined bounded self-adjoint operator) T:H\rightarrow H 其特征值序列是不可计算的。并且其范数(norm)是一个不可计算实数。

    这是否证明了“我们的宇宙具有不可计算的属性。”就仁者见仁,智者见智了。

     

    • Arkady Bolotin 认为构成量子理论的数学基础本身涵盖了不可计算性且无法避免。

    量子力学中使用了一个无限可分的希尔伯特空间,线性算子作用于其中。希尔伯特空间 \mathcal{H} 的可分性(separable)意味着 \mathcal{H} 承认一个标准正交基(orthonormal basis),它由一个可数的向量族组成。而向量族 \left\{ |\Phi_{n}\rangle \equiv |n\rangle_{n\in\mathbb{N} } \right\} 满足正交化(orthonormalization)关系: \forall m,n\in\mathbb{N}:\langle m|n\rangle =\delta_{mn} 以及闭包(closure)关系:

    \sum_{n=1}^{\infty}{|x\rangle \langle n|=\mathbb{1}_{\infty}}\,\,\, \left( A\right)

    \mathcal{H} 的标准正交基。而后可分希尔伯特空间 \mathcal{H}|\Phi\rangle 可拓展为: |\Phi\rangle =1_{\infty}|\Phi\rangle=\sum_{n=1}^{\infty}{|n\rangle\langle n|\Psi\rangle}

    其中 \Psi\equiv\langle n|\Psi\rangle \in\mathbb{C} 定义了 |\Psi\rangle 的 numerical representation。然后一个线性算子 L 在希尔伯特空间 \mathcal{H} 中为线性映射: L:\mathcal{D}\left( L \right)\rightarrow\mathcal{H}\,\, and\, \, |\Psi\rangle \rightarrow L|\Psi\rangle 其中 \mathcal{D}\left( L \right) 定义了算子的定义域。使用 \left( A \right) 任何线性算子 L 作用于无限可分希尔伯特空间 \mathcal{H} 都可以表示为: L=1_{\infty}L1_{\infty}=\sum_{m,n}^{\infty}{\langle n|L|m\rangle |n\rangle\langle m|}

    其中 L_{mn}\equiv\langle n|L|m\rangle \in\mathbb{C} 定义 L 的 numerical representation。

    上述式用于在无限维希尔伯特空间 \mathcal{H} representation 和 number-based representation之间进行转换。

    Arkady Bolotin 亦认为一个人无法写下一个 numerical vector: \overrightarrow{\Psi_{\infty}} =\left( \Psi_{1} ,...,\Psi_{n},..\right) 或者是一个 numerical matrix : \mathbf{L_{\infty}}=\left( L_{nm} \right)_{nm}^{\infty} 。因为这些对象包含了无限数量的元素。此外,对这些数值对象的运算,比如说: ||\overrightarrow{\Psi_{\infty}} ||^{2}=\Sigma_{n=1}^{\infty}|\Psi_{n}|^{2} 以及 \mathrm{Tr}\left ( \mathbf{L_{\infty}} \right )=\Sigma_{n=1}^{\infty}L_{nn} 可能需要进行无限求和(infinite summations)。更重要的是,任何试图将这些无限的向量和矩阵规成一个有限序列(以便使它们显式和对它们的运算都很明确)的尝试会立即导致与正则对易关系(canonical commutation relation,CCR)发生冲突:即量子力学中规范共轭量( conjugate quantities)的基本关系。

     

    对于物理系统确切地可计算函数与图灵机可计算函数之间是否可以画上等号的探讨还在继续,目前图灵机架构已经为可计算性给出了一个极限,然而至于对于物理来说这个可计算极限到底在哪里:牛顿经典物理学的连续时空是可以构造超越图灵机的机器的;广义相对论的特定时空也可以做到;然而量子理论却达不到要求。

    正如 Konstantine Arkoudas 所写的:

    ... 古典派学者的观点是:图灵可计算函数构成了物理可实现计算的最大类。如果超计算的拥护者声称图灵可计算函数并没有形成一个最大的物理可计算函数类,那么他们就应该指出哪些函数是物理可计算的。有以下三种可能性:
    1. 任何地方都没有设置限制。所有的函数都是物理可计算的。
    2. 这个限制是根据图灵机的极限(或者甚至可能是在图灵机之下)设置的。
    3. 这限制是在上面两点之间的某个地方设置的。
    第一种选择是物理泛可计算性,这是非常难以置信的,它将可计算性降低到无关紧要的程度。第二个选择反映了古典派学者的信念。因此,人们会得出结论,超计算的拥护者会提倡第三种选择 ... 注意,一个纯粹的数学模型,如 oracle machine ,coupled Turing Machine 等等,将不符合我们的要求。我们必须要知道哪些物理定律(以经验可证伪为准)会设法在所有的函数类中画出一条线(区分真正可计算与不可计算的),并且确切地知道这条线的准确位置。事实上,实现这种划分是超计算拥护者的一个重要愿望。...

     

    既然物理理论上允许不可计算的现象存在,在最乐观的情况下,可以用于制造突破现有计算设备根本限制,不受丘奇-图灵论题约束的强力装置:超计算机(Hypercomputer),完成跨越图灵屏障(Turing's barrier)。做到:

    • 由不可计算的物理现象构成的 Hypercomputer 至少可以帮助我们完成一个经典图灵机做不好的任务:仿真它自己。因为经典图灵机的有限步运算无法给出有界连续变量的大多数取值,只能做近似模拟。而且不可计算性会导致初始条件精确已知时依然难以做长期预测,而可计算的混沌则会失去作用。单纯的混沌现象在不可计算现象面前根本就是小巫见大巫
    • Hypercomputer 可以帮助我们访问图灵机不能访问的更高阶层的 arithmetical hierarchy和 degrees of unsolvability。解决图灵机不可判定问题。
    • Hypercomputer 可以用来构建非递归枚举的形式系统。最重要的是,非递归枚举形式系统不受哥德尔不完备性的限制。

     

    P.S.比如说 True arithmetic ,即把所有在(N,0,1,+,*)上成立的一阶语句抽取出来,令数论中的所有真命题组成一个集合,把里面所有的真命题当作公理。这样的形式系统既包涵了皮亚诺公理(足够强),又是自治完备的。自治性与完备性兼得且两不误。那么哥德尔不完备性对它无效。不过我们是没有办法构建这样强大的形式系统的,因为它们对于我们来说是不可计算的。由于它的不可计算性,其次是因为使用图灵机的话我们很可能无法在一个有限时间里获得它的公理 (因为它是非可枚举的。)。想要获得非可枚举形式系统中的公理,除非使用超计算。

    具体的:True arithmetic 为所有在 Peano arithmetic {\displaystyle {\mathcal {N}}} 中为真的一阶算术语句集合,记作 \mathrm{Th}( {\displaystyle {\mathcal {N}}}) 。并且 \mathrm{Th}( {\displaystyle {\mathcal {N}}}) 不是算术可定义的(arithmetically definable)。

    \mathrm{Th}_{n}( {\displaystyle {\mathcal {N}}})\mathrm{Th}( {\displaystyle {\mathcal {N}}}) 的子集,并且其只包含在算术层级中为 \Sigma_{n}^{0} 或更低的语句(关系)。不过对于高于 \Sigma_{n}^{0} 的关系来说 \mathrm{Th}_{n}( {\displaystyle {\mathcal {N}}}) 是算术可定义的。并且: {\displaystyle {\mbox{Th}}({\mathcal {N}})=\bigcup _{n\in \mathbb {N} }{\mbox{Th}}_{n}({\mathcal {N}})}

    最重要的是, \mathrm{Th}( {\displaystyle {\mathcal {N}}}) 的图灵度为 0^{(\omega)} 。这表明,True arithmetic 是高阶不可计算的,且表达能力极其强大。

     

    特别地,对于那些可能会在物理上得到实现的模型,Konstantine Arkoudas 也给出他的看待:

    ... 事实上,即使是一项非常严谨的数学结论证明了一些超计算模型提议与某些物理理论的原理是一致的 ... 然而这并没有任何实际意义,除非这种装置(或至少是它的一个原型)被建造并且成功测试之前,原因在于毕竟这是经验科学。
    据我们所知,这种证据所依据的一些科学原理可能是错误的。可证伪性一直是科学理论接受的命运,没有任何理论可以作为这种命运的先天例外。第二,到目前为止,我们还没有关于真正正确的关于“万物理论”的物理理论 ...
    因为一个理论的兼容性参数可能会与另一个理论相冲突。也就是说,不与一个理论冲突的假设可能会对另一个理论产生问题。例如,旨在表明一些 Supertask 与广义相对论相容性的思想实验可能会违反量子力学或热力学的物理约束 ...
    最后,所有的科学理论都提出了自身的理想化结构,而这种理想化的结构是否会真正与那些声称是超计算的奇异、精巧的装置构造和操作有关,还远不清楚。要证明一个理论上有争议的计算设备在物理上的合理性,唯一的方法就是建立一个原型。

    当然最悲观的可能性就是:这些不可计算现象仍然是不可能利用的。可实行的计算最终还是脱离不了图灵机的能力范围,图灵屏障仍旧无法跨越。那么还有一件事情是很值得做的:弄清楚这种异常背后的原因。

    展开全文
  • 计算机的本质是什么?逻辑?数学?

    千次阅读 多人点赞 2019-07-01 08:00:00
    虽然在今天看来ENIAC计算能力连手机,甚至是十几块钱的计算器都比不上,但它在当时却是相当强大。ENIAC的体积非常庞大,得好几个大房间才能放下它,耗电也相当恐怖,开机全城家家户户电灯都要变暗。 之所以称...
    
     

    计算机的诞生

    1946年,在美国的宾夕法尼亚大学诞生了第一台现代电子计算机ENIAC。虽然在今天看来ENIAC计算能力连手机,甚至是十几块钱的计算器都比不上,但它在当时却是相当强大。ENIAC的体积非常庞大,得好几个大房间才能放下它,耗电也相当恐怖,一开机全城家家户户电灯都要变暗。

    之所以称ENIAC是第一台现代计算机,是因为现代计算机理论的奠基人是图灵和冯诺依曼。这两个超级天才应该大家都听过,图灵提出了图灵机理论模型,而冯诺依曼设计确定了现代计算机的基础结构,他以数学语言阐述了计算机模型,将程序和数据都存在存储器中。

    640?wx_fmt=jpeg

    timg

    思想转为代码

    实际上,计算机的发展并非一蹴而就。现代电子计算机属于狭义上的计算机,而广义上的计算机其实包括所有人类制造出来的计算设备,比如古代的算盘也属于计算机,只不过它是靠人力驱动的,再比如机械式计算机,使用机械齿轮来进行运算。

    640?wx_fmt=jpeg

    image

    在广义上,对于计算机我们更应该将其理解为一种思想。计算机其实是为了帮助人类将思想转化为代码仿真出来,这就要求我们需要先对思想进行解码工作。而在古代就已经有先贤在逻辑学和数学方面进行研究,其中最伟大的思想家就是柏拉图和亚里士多德,他们俩也互为师生关系。

    亚里士多德首次将哲学与科学分离,并在逻辑方面进行了研究,他认为逻辑是一切科学的基础,是形式逻辑学的创始人奠基人。他将人的思维和存在联系起来,然后根据实际阐明逻辑。亚里士多德在推理逻辑中提出了三段论:

    所有动物都会死所有人都是動物所以,所有人都會死
    所以,所有人都會死
    

    异类联想

    自亚里士多德以来,逻辑学和数学都是分开研究各自发展的。直到后来德国的莱布尼茨哲学家才尝试将它们结合起来,通过将两种现有的思想结合起来,以形成第三种创新思想,即异类联想。后来发展出数理逻辑这门学科,以数理逻辑思想为基础的计算科学也在不断地发展着。对于这些人,他们的目标是将抽象的逻辑用精确的数学符号来表示,

    对于计算机,多数人会认为计算与逻辑是密不可分的,甚至还有人认为计算的本质其实就是逻辑。而逻辑与数学的关系是,逻辑并不等于数学,只是曾经有人想以逻辑为基础来构建数学。逻辑、计算和数学三者应该如何融合?

    640?wx_fmt=jpeg

    image

    调和代数与几何

    在笛卡尔之前,代数和几何各自为政,它们是两个独立不同的学科。然而几何过度依赖图形与形式,代数又过分受公式限制,这都制约了它们的发展。这时法国数学家笛卡尔则通过异类联想将这两者联系了起来,创立了解析几何,从而他也被称为解析几何之父。

    笛卡尔发明了现在大家很熟悉的直角坐标系,x轴和y轴,通过坐标系成功调和了几何与代数。从此一个圆可以用方程来描述,也可以用坐标系画图来表示。此外,解析几何也为微积分的创立奠定了基础。

    640?wx_fmt=jpeg

    image

    逻辑与代数的融合

    现在估计多数人都没听过布尔,程序员最多也是知道布尔类型,但其实可以说布尔逻辑是计算机的核心理论。莱布尼茨一直的梦想就是将逻辑学和数学进行融合,而英国的数学家乔治布尔则通过异类联想将亚里士多德的三段论与代数结合起来,并发明了二进制,将这个梦想向前推动。

    算术可来实现加法乘法,而逻辑主要是或、与等,能否将它们结合起来呢?逻辑或类似于加法,即两个相交集合中,有些元素只属于其中一个集合。逻辑与则是两个相交集合共同拥有的那些元素,这部分类似于乘法。而且是只有在0和1的情况下才能成立,这就将算术与逻辑通过二进制运算连接了起来。

    640?wx_fmt=jpeg

    image

    香农的二进制

    正是克劳德香农将布尔的逻辑运算带入计算机,香农是一名贝尔实验室的工程师。比起有名的科学家,香农的名气不算大,估计只有计算机专业的人有了解过他,而且大家知道他估计也是因为信息论。其实香农的伟大成就还包括他将逻辑融入到计算机内,从而成功将逻辑层和物理层进行分离。得益于香农将逻辑映射到现实物理世界,至此计算机得到了空前的发展。

    640?wx_fmt=jpeg

    image

    其实是他将二进制运算与电子器件相结合,实现了逻辑功能,奠定了如今计算机的运算机制。他设计出了相加电路来构造复杂的算术运算,这些电路也成为现代计算机的组件。纵使后面越做越小越来越先进的晶体管,也是基于香农的电路原理。

    640?wx_fmt=jpeg

    image

    图灵的图灵机

    图灵机即图灵计算机,是由数学家艾伦·麦席森·图灵(1912~1954)提出的一种抽象计算模型。图灵尝试以数理逻辑语言来设计计算机,将人们使用纸笔进行数学运算的过程进行抽象,由一个虚拟的机器替代人们进行数学运算。

    图灵机有一条无限长的纸带,纸带分成了一个一个的小方格,每个方格有不同的颜色。一个机器头在纸带上进行移动,机器头有一组内部状态,还有一些固定的程序。在每个时刻,机器头都要从当前纸带上读入一个方格信息,然后结合自己的内部状态查找程序表,根据程序输出信息到纸带方格上,并转换自己的内部状态,然后进行移动。

    每一个会决策、会思考的人都可以被抽象地看成一台图灵机,该模型主要有四要素:输入集合、输出集合、内部状态和固定的程序。如果把人进行抽象,那么输入集合就是所处环境中所看到、听到、闻到、感觉到的一切;输出集合就是人的每一言每一行,还有表情动作;内部状态集合则可以把神经细胞的状态组合看成一个内部状态,所有可能的状态集合将是天文数字。

    640?wx_fmt=jpeg

    这里写图片描述

     

    -------------推荐阅读------------

    我的开源项目汇总(机器&深度学习、NLP、网络IO、AIML、mysql协议、chatbot)

    为什么写《Tomcat内核设计剖析》

    2018汇总数据结构算法篇

    2018汇总机器学习篇

    2018汇总Java深度篇

    2018汇总自然语言处理篇

    2018汇总深度学习篇

    2018汇总JDK源码篇

    2018汇总Java并发核心篇

    2018汇总读书篇

    跟我交流,向我提问:

    在这里插入图片描述

    欢迎关注:人工智能、读书与感想、聊聊数学、分布式、机器学习、深度学习、自然语言处理、算法与数据结构、Java深度、Tomcat内核等相关文章

    在这里插入图片描述

     

    展开全文
  • 计算机组装与维护试题及答案

    万次阅读 多人点赞 2014-12-06 15:59:39
     填空 1 CPU 的外频是100MHz ,倍频是 17 ,那么 CPU 的工作频率(即主频)是(1.7)GHz 2 在拆装微机的器件前,应该释放掉手上的(静电) 3 系统总线是CPU与其他部件之间传送数据、地址等信息的公共通道...
  •   是由数学家阿兰·麦席森·图灵(1912~1954)提出的一种抽象计算模型,即将人们使用纸笔进行数学运算...机器头有一组内部状态,还有一些固定的程序。在每个时刻,机器头都要从当前纸带上读入一个方格信息,然后...
  • 计算机三级网络技术考过指南

    万次阅读 多人点赞 2018-03-10 19:18:36
    下面记忆一下,做题时会比较方便(不要畏难,做题见多了就记住了) 二进制 十进制 1000 0000 128 1100 0000 192 1110 0000 224 1111 0000 240 1111 1111 ...
  • 本文目录、考研大纲1. 计算机发展的历程2.计算机的层次结构计算机系统的基本组成计算机硬件的基本组成计算机的软件与硬件的关系计算机的工作过程(指令执行的过程)3.计算机的性能指标 ==(重点)==二、计算机发展...
  • 系统性学习计算机(

    千次阅读 2018-10-13 16:53:20
    计算机(computer)俗称电脑,是种能够接收和存储信息,并按照存储在其内部的程序(这些程序是人们意志的体现)对输入的信息进行加工,处理,并且把处理结果输出到高度自动化的电子设备。计算机由硬件设备及软件...
  • 计算是思科创造的个术语,由OpenFog Consortium支持,该联盟由Arm、思科、戴尔、英特尔、微软和普林斯顿大学边缘实验室于2015年成立。其使命宣言(部分)内容如下: 我们的工作将定义分布式计算、网络、存储、...
  • 、有限状态 引子 让我们先来看几个简单的概念: 状态 - 系统的基本数学特征。 状态 - 个离散数学模型。给定个输入集合,根据对输入的接受次序来决定个输出集合。 有限状态 - 输入...
  • 来源:华为试题2描述写出程序,接受个有字母和数字以及空格组成的字符串,和个字符,然后输出输入字符串中含有该字符的个数。不区分大小写。知识点字符串,循环运行时间限制0M内存限制0输入输入个有字母...
  • 、数码舵机与模拟舵机的区别 传统模拟舵机和数字比例舵机(或称之为标准舵机)的电子电路中无MCU微控制器,一般都称之为模拟舵机。老式模拟舵机由功率运算放大器等接成惠斯登电桥,根据接收到模拟电压控制指令和...
  • 数字图像处理:4.色彩空间转换

    千次阅读 2013-07-30 20:46:31
    而颜色可以由不同的角度,用三个一组的不同属性加以描述,就产生了不同的颜色空间。但被描述的颜色对象本身是客观的,不同颜色空间只是从不同的角度去衡量同一个对象。 颜色空间按照基本结构可以分两大类:基色颜色...
  • 从有限状态图灵到现代计算机

    千次阅读 2014-12-13 10:55:01
    、有限状态 引子 让我们先来看几个简单的概念: 状态 - 系统的基本数学特征。 状态 - 个离散数学模型...课本中的组合电路+时序电路的模型就是个有限状态,我们不妨通过它来推测有限状态应有的
  • 数字电视 顶盒原理

    万次阅读 2011-12-13 16:55:31
    数字机顶盒的故障分析诊断和检修单元 卫视家族! ]( ? ]2 H4 T. f) Q5 E% Q- e. I 数字机顶盒工作原理和电路分析qbox.5d6d.com/ n8 H; ^' }) Y5 V/ o 有线电视系统卫视家族6 @6 b* W; @$ c0 V0 B 0 \" E$ g3 n/...
  • 二,八,十,十六进制转换

    千次阅读 2012-11-13 22:46:55
    1 数制的概念 ...在计算机中采用的是二进制,它的特点是“逢二进”,因此只有0和1两个数字符号,计算机较容易实现。在程序设计中,十六进制常用作二进制的压缩形式,位十六进制数可表示四位
  • 图灵计算问题

    万次阅读 2007-08-03 12:55:00
    自从20世纪30年代以来,图灵计算这些重要的概念在科学的天空中就一直闪烁着无限的光彩。尤其是近年来量子计算机、生物计算机、DNA计算等领域的创新工作引起了世人的广泛关注。我们不禁问这样的问题,国外究竟为...
  • 1 整体介绍相机标定为Matlab工具箱 http://www.vision.caltech.edu/bouguetj/calib_doc/ 相机标定为Matlab工具箱 ...这是个释放相机标定为Matlab工具箱 庐 完整的文档。... 这个文档可能 也被用作个教程自它
  • 计算机级考试 试题及其答案

    千次阅读 2011-03-12 22:15:00
    1. 根据计算机使用的电信号来分类,电子计算机分为数字计算机和模拟计算机,其中,数字计算机是以( )为处理对象。 A)字符数字量 B)物理量 C)数字量 D)数字、字符和物理量2. 下列关于世界上第台电子计算机...
  • 2楼 : JAVA篇 此篇收录:.《Java 2 核心技术》、2....《C程序设计语言》、2.《C和指针》、3.《C陷阱与缺陷》、4.《C专家编程》、5.《你必须知道的495个C语言问题》 4楼: C++篇 此篇收录:1.《C++ Primer》、2
  • 计算机三级嵌入式学习笔记(

    万次阅读 多人点赞 2021-02-05 15:49:28
    计算机三级嵌入式学习笔记()-- 嵌入式系统概论
  • 200个经典C程序【源码】

    千次下载 热门讨论 2013-08-08 10:48:40
    026 阿拉伯数字转换为罗马数字 027 字符替换 028 从键盘读入实数 029 字符行排版 030 字符排列 031 判断字符串是否回文 032 通讯录的输入输出 033 扑克牌的结构表示 034 用“结构”统计学生成绩 035 报数...
  • 计算机组成原理(白中英) 第章 课后题答案

    千次阅读 多人点赞 2020-03-05 19:30:29
    冯诺依曼计算机体系结构核心思想...程序或指令的顺序执行,即预先编好程序,然后交给计算机按照程序中预先定义好的顺序进行数值计算。 为什么冯诺依曼体系结构选择二进制? 答:①两个状态的系统在物理上容易实现...
  • 计算机文化基础—计算机硬件系统

    千次阅读 2017-03-16 17:12:00
    第2章 计算机硬件系统 本章内容 信息工具——计算机 计算机的工作原理 微机系统及其主要指标 嵌入式计算机系统 ... 人类所使用的计算工具从简单到复杂、从低级到高级的发展...1946年2月,世界上第数字电...
  • 计算机组成原理

    万次阅读 多人点赞 2018-10-18 08:44:14
    冯诺依曼提出“存储程序”原理,即把程序本身当作数据来对待,程序和该程序处理的数据用同样的方式储存,以此为基础的计算机称为冯诺依曼。特点: ①计算机由运算器,控制器,存储器,输入和输出五部分组成 ②指令和...
  • 他们还建立了个大规模人脸扫描数据库,用于训练这个系统。实验证明,该系统比当前常用的最好模型表现优异许多,可以将任意角度拍摄的 2D 快照生成逼真的 3D 人脸。Science 对此作了报道,标题中提到“计算机科学家...
  • 计算机组成原理核心知识点总结&面试笔试要点

    万次阅读 多人点赞 2019-08-13 14:04:07
    作为名计算机专业的学生,计算机组成原理、计算机网络、操作系统这三门课程可以说是专业核心基础课,是至关重要的,其内容是名合格的coder所必备的知识集;非科班出身的程序员要是想要有所提升,也需要认真学习...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 104,507
精华内容 41,802
关键字:

一组数字转换机按下面的程序计算