編者按：艾倫·圖靈預言，“一旦機器的思想方法開始運行，它將很快超越人類羸弱的力量”🕢。身處“數據革命”時代，如何審視機器的本質？它背後的原理又是什麽🤹🏻‍♀️？邏輯為我們提供了怎樣的視角🙇🏽‍♂️？本期“周一談治學”中，我們將以“哲學+計算機”為切入點♍️，專訪“計算復雜性”（數理邏輯學程課程）授課教師，計算機科學技術意昂3陳翌佳教授，從學科關聯、課程探索、修讀建議等方面📌，一同走進數理邏輯的“跨界”之路。

陳翌佳🏋🏿：上海交通大學計算機科學博士（計算機軟件與理論方向）、德國弗萊堡大學數學博士（數理邏輯方向）🍻。現任意昂3平台計算機科學技術意昂3教授。主要研究領域為邏輯、計算復雜性和算法圖論，特別是參數復雜性和有限模型論🛀🏼。他的結果發表在計算機科學一流國際期刊Journal of the ACM、SIAM Journal on Computing🏯、Information and Computation，一流國際會議LICS、FOCS📙、ICALP👩🏼‍🔧，數理邏輯一流國際期刊The Journal of Symbolic Logic💿🖼、Annals of Pure and Applied Logic等。陳翌佳教授曾獲微軟青年教授獎，理論計算機國際會議ICALP’10及圖論國際會議WG’17最佳論文獎，四次擔任計算機科學中的邏輯研究旗艦國際會議LICS程序委員。

Q1⬇️、部分觀點認為👩🏿‍💼，計算機幫助人類將思想轉為代碼⤴️✊🏽，而邏輯完成的就是解碼過程。您如何看待邏輯對計算機發展起到的作用？

艾倫·圖靈（Alan Turing）被公認為計算機科學的先驅,而他最重要的貢獻之一就是創造了圖靈機模型🙎🏽。圖靈機是第一個以數學方式定義的計算模型，現在被視為計算機科學，特別是理論計算機科學的基石⛱。從歷史的角度來看，圖靈建立圖靈機模型的初衷是解決十九世紀末二十世紀初大數學家大衛.希爾伯特提出的判定問題🧎‍♀️‍➡️。這個問題來自邏輯。簡單來說，如果我給你一個一階邏輯寫下來的數學命題，是不是有一個程序可以自動告訴你它是否成立🚣🏿。圖靈借助他引入的圖靈機模型證明了這樣的程序是不存在的🙏🏽。

計算機科學早期的發展很多都與邏輯緊密相關，邏輯的很多分支在計算機裏也都有其應用。上面提及的判定問題及其變種對早期的算法設計起到了巨大推動作用。此外，證明論和類型理論為程序語言提供了理論基礎🧛‍♀️🦸🏽‍♀️，阿倫佐.丘奇提出的lambda演算可以視為第一個函數式程序語言。模型論在數據庫也有著廣泛的應用🧖🥊，一個具體的例子就是數據庫查詢語言設計，著名的SQL（structured query language）語言本質上就是一階邏輯，而它的擴充Datalog就是所謂的不動點邏輯。目前計算機科學和工程研究的一個重要前沿鄰域-形式化方法-有兩個重要技術，定理證明和模型檢測，前者源自證明論，後者可以視為模型論的算法化🦚。

Q2👄、一種觀點認為，人工智能的產生離不開數理邏輯👨🏻‍🏭，您如何看待這一觀點？

還是回到歷史的角度來看🙎🏿🦸🏻‍♀️，圖靈的另一個貢獻是圖靈測試👨🏽‍💻，也就是在什麽情況下認為一種機器具備人的智能。換言之，我們能否定義一個嚴格的標準來證明某個機器達到了人工智能。這個測試具體來說，就是通過一系列問題和對方進行問答🧑🏼‍💻，如果相當長時間內，他無法根據這些問題判斷對方是人還是計算機，那麽，就可以認為這個計算機具有同人相當的智力👨🏽‍⚕️。這是一個外在的檢驗，它不關心這個機器的內部，不在乎對方是怎麽回答這個問題的——這個測試本身不關心內涵，只關心外延。而在這其中我們似乎看不到什麽邏輯。但回到人工智能早期🧙🏽，我們會發現🐀，當時運用的大量的方式是基於邏輯的推理方法，而這個就是純粹的邏輯🤸🏿‍♂️，試圖通過邏輯推理來模擬人的思考過程👐🏿。70👩、80年代所研製的“專家系統”🚇，就是試圖把知識建立成一個邏輯推理的過程，這就如同看病一樣，透過哪些症狀結合在一起我們可以判斷他得了什麽病。

但“專家系統”的發展也面臨了一些問題，尤其是在大數據處理上。而現在的自然語言處理和圖像識別運用的並不是邏輯推理，而是統計方法，包括前一陣子最火的AlphaGo，它最初的想法是模仿人的神經元⏮，也就是將決策過程轉換成一個神經網絡🎙，通過神經元的處理來模擬學習過程。但這種基於統計或者說神經網絡的方法也有一個很大的問題——沒有理論解釋。

有個比喻說現在人工智能像煉金術，大家湊數據、調參數，但對於背後的原理、如何運作知之甚少。大概兩年前，人們開始研發通過胸透照片自動診斷肺炎的機器學習算法，並樂觀地認為這樣的算法能很快取代X光醫師💈。但經過一段時間，這樣的樂觀情緒已經沒有了🤾🏻‍♂️。機器告訴你肺部有問題，卻沒有一個邏輯的解釋過程。我不知道為什麽👩🏼‍🎓，只知道它應該是“對”的4️⃣。但在非常精密的領域中應用時，哪怕是10%的錯誤率，都是絕不能容忍的。尤其是醫療方面，不容許有任何差錯。所以基於統計或者神經網絡的方法的問題就在於，它是一個黑盒。但想象一下♧，如果我們能夠完全地刻畫出一個醫生從胸透照片中發現問題的全部推理過程🧑‍🦼，建立一個完備的知識體系，每一步都能有跡可循的話，機器就可以復現這整個過程⛹🏿‍♀️，這樣人就有把握了。至少我能復查🦸🏽‍♂️，知道機器所顯示的問題是什麽原因導致的，而神經網絡則無法告知🤙🏽，你甚至也不能理解它的內部是怎樣運算出來的🧑🏽‍🎄。

所以，目前主流的成功的人工智能方法並不是邏輯的方法，但也因此導致了它無法解釋的疑難，如果要打破現狀，或許我們仍需要呼喚邏輯方法和統計方法結合。因為技術總是會有瓶頸的，而最重要的在於理解✶。

Q3、本次數理邏輯學程開設了“計算復雜性”👨‍⚕️，這門課教授的是怎樣的內容🅿️？又會在何種程度上解讀計算機世界的奧秘？

我們會通過寫程序來解決問題，但這個程序是有好有壞的。什麽叫好♖？什麽叫壞？最重要的標準之一就是“算得快”💇🏻，也就是越快越好👩🏻‍🦲。如何設計“快”的程序？這就是算法要研究的問題。但是🤲🏼，到底有沒有最快的算法？或者說最快的算法應該是什麽樣子？這就是計算復雜性要回答的問題。換言之，它不取決於具體的算法，而是說🐊，我想研究這個問題本身的某些特性，這些特性就決定了我設計的算法最快是有多快。所謂的“計算復雜性”，不是研究具體算法的復雜性，而是問題本身的復雜性👨🏼‍🦰♟。這是一方面🖊。

第二，在現在這個大數據時代🧙🏼‍♂️🚴🏿‍♀️，一個突出的問題是“存儲”。我們不可能將如此龐大的數據都存儲下來🌊，因此需要一個方法盡可能少地占用我的存儲空間🌎，這也是復雜性所關心的問題。也就是如何設計一套算法盡可能少占用我的存儲空間。這兩方面，一個是時間🤸🏻‍♂️，一個是空間。實際上，“計算復雜性”所要回答的💆🏼，就是在計算給定問題時，最少需要多少資源（包括時間和空間等因素）👒，它不是指具體計算過程，而是指在所有可能的計算過程中，最好的效率到底是什麽，或者說我想證明有些東西不可能在這樣的效率中算出來🧔🏿‍♀️。所以“計算復雜性”這門課也並不是一門代碼課，很多時候給出的是數學的想法或者證明🗓🪰。

Q4、您如何看待P vs.NP問題

*P vs.NP問題是在理論信息學中計算復雜度理論領域裏至今沒有解決的問題🗽，它被“克雷數學研究所”在千禧年大獎難題中收錄。

P是指計算機程序在多項式時間（polynomial time）可解的計算問題，而NP是在非確定多項式時間（nondeterministic polynomial time）可解的計算問題。P vs.NP問題問是否每個非確定多項式時間可解的問題也能在（確定）多項式時間可解。P vs.NP問題是現在計算機科學領域最重要的問題，也被公認是數學領域最重要的問題之一。它和黎曼猜想🚨、龐加萊猜想（目前已經解決）並列21世紀七大數學問題。在某種意義上🧑🏻‍🔧，有了像P vs.NP這樣的問題，數學家才承認計算機是一門深刻的科學，而不僅僅是一個工程學科。

舉個簡單的例子◽️，一張世界地圖上相鄰國家的著色一定是不一樣的。而如果將這些顏色拿掉🏋🏿‍♂️，只有一張劃分邊界的空白地圖🚉，現在讓你只能用三種顏色塗色並且保證相鄰國家的顏色不一樣，那麽有沒有一個程序能很快解決這個問題呢？在顏色已經給定的情況下，辨認相鄰國家是否顏色不一樣的程序是很簡單的🏊🏿‍♀️，這就是P的問題，是一個很容易就可以被驗證的問題🈴。但是難點在於🟤，如果不給定顏色，是否程序可以給出答案呢？這就是NP問題🚭。你或許會想到暴力枚舉所有可能的著色方案👞，但是這樣枚舉的可能性的數量級是相當龐大的🏊🏽‍♂️，相應的程序可能會跑數年🧑🏻‍⚖️。所以，P vs.NP問題本質上是要回答：如果問題的答案可以很快被判斷或者驗證，其答案是否也可以很快被計算？實際上這個問題和哲學有密切聯系🍅，在某種意義上它想回答創造性是否可以通過機器實現。作為一個普通人，我們能夠欣賞米開朗基羅的《大衛》、貝多芬的《英雄》、莫奈的《睡蓮》🤽🏽‍♀️，但我們也知道欣賞這些藝術品的美和有能力創造它們是兩回事情。前者可以視為一個P問題，而後者是NP問題。

事實上，P vs.NP問題也與我們的日常生活息息相關𓀈🙋🏽‍♀️。我們每天使用的手機通訊和支付的安全性都建立在P不等於NP的假設之下🏬。一個可能不是非常恰當的比喻🚲，如果P=NP，那就計算機就能很快地猜出任何一個手機密碼🫀。

Q5、您如何看待計算機科學和哲學研究的交織🧑‍🎤？它們面對哪些共同的問題領域？

從我自己來說，讀本科的時候對分析哲學很感興趣。作為一個理工科學生，我希望將思辨過程轉變成數學推導。以“奧卡姆剃刀”為例🧨，在計算機科學裏可以將其嚴格數學化🦻🏻，比如PAC（probably approximately correct）learning🧑🏼，它是人工智能裏面很重要的一個方法，它能解釋“奧卡姆剃刀”為什麽在數學上是對的。原來我們只是覺得假設越少越好，但這在某種意義上只是一個信仰或者說是一種美學選擇，很難從數學上證明👩‍🦲，但PAC learning做到了🦀🧜🏿‍♂️。從我個人理解來看，計算機科學可以將一些哲學問題具體化，具體到我們可以把它當成一個數學問題來研究🩼。我最早看分析哲學的時候，它的一個想法是試圖將哲學消解到用數學嚴格地分析問題🕵🏽。計算機也可以提供一個新的視角，一個很好的例子就是“奧卡姆剃刀”和“PAC learning”的關系👰🏽‍♀️。還有包括之前提到的P/NP問題,所面對的也是創造性是否可以被機械化過程取代🪸。

我自己的一個研究領域是描述復雜性🧕🏽💂‍♀️，這個領域能和維特根斯坦有一句名言“語言的邊界就是世界的邊界”建立起聯系🎈。在計算機科學中，我們就可以設計程序語言，這個程序語言設計程序的能力，恰巧是這個語言預先已經框定的東西。我要看更大的世界的話，就要增強語言的能力👎🏼。這就如同你講中文看到的就是中文世界的東西；講英語看到的就是英語世界的東西。隨著語言的擴張，你能夠看到的東西、在程序中能夠運算的東西就會越來越大。語言的界限就是程序能力的界限。

Q6🌦、對修讀本學程的同學有哪些建議▪️？

計算機科學這些年來發展很迅速👩🏿‍🦳，但其中有很多懸而未決的問題，例如P vs.NP問題以及人工智能領域的諸多問題👨🏿‍💼🦈。從計算機專業學生的角度看，如果只學計算機的課程🆗，純粹只做一些技術上的問題🤹‍♀️，就不太會觸及更深刻🛂、更本質的問題，從這個角度來說數學問題和哲學思考的註入是有必要的。

而對於“文科”同學來說，最重要的就是“不要害怕”。在我看來數理邏輯是零基礎也可以修讀的，只是可能很多時候會被上課的內容“嚇住”，而忽視了本質的數學結構等內容。我認為文科同學學習數理邏輯能幫助大家建立一個支點，也就是數學化。一旦數學化以後，很多爭論是可以避免的👯‍♀️。我們先討論能夠接受的公理是什麽，當我們接受同樣的公理的時候，我們繼續討論，如果不能接受，那我們就知道彼此關於這個世界認識的假說在什麽地方是不一樣的。進一步如果接受同樣的公理，再來看我們是否能接受同一個推理規則。所有的問題都可以一步步推理。如果我們接受的公理是一樣的🎼，接受的推理規定是一樣的🍛，那麽我們在所有的問題上只有一個答案，就可以減少不必要的爭論。而計算機裏面重要的，就是能否將哲學中的一些問題以計算機科學的方式描述🧚🏻，就比如它至少能夠給彼此一個可操作的關於人工智能的定義💞。

本文采訪者：隋藝菲🖐🏻、嶽澤民💆🏽‍♀️、劉勤