Reductions鄧小鐵上海交通大學(xué)Reductions鄧小鐵計(jì)算機(jī)科學(xué)的Reduction計(jì)算機(jī)科學(xué)的Reduction（vonNeuman的電腦ENIAC）（vonNeuman的電腦ENIAC）計(jì)算機(jī)科學(xué)計(jì)算機(jī)科學(xué)計(jì)算機(jī)應(yīng)用計(jì)算機(jī)應(yīng)用邏輯電子元件邏輯電子元件邏輯電子線路用AND-OR-NOT元件組合的線路Universal：可以計(jì)算任何（變量有限）的邏輯函數(shù)應(yīng)用領(lǐng)域自動(dòng)機(jī)計(jì)算機(jī)，空調(diào)，電梯，洗衣機(jī)，電視，手機(jī)，GPS導(dǎo)航，電子游戲，以及許多我們今天已經(jīng)難以離開的現(xiàn)代電子科技產(chǎn)品。邏輯電子線路用AND-OR-NOT元件組合的線路可計(jì)算性理論可計(jì)算性理論可計(jì)算性理論圖靈機(jī)有限態(tài)控制器：狀態(tài)集合，字母集合，轉(zhuǎn)移規(guī)則輸入／輸出紙帶等價(jià)計(jì)算體系遞歸函數(shù)λ演算可計(jì)算性理論圖靈機(jī)Hilbert（第二）問題數(shù)學(xué)是完備的嗎？

面對那些正確的數(shù)學(xué)陳述，我們是否總能找出一個(gè)證明？數(shù)學(xué)真理是否總能被證明？Godel:

No數(shù)學(xué)是一致的嗎？數(shù)學(xué)是否前后一致，不會得出某個(gè)數(shù)學(xué)陳述又對又不對的結(jié)論？數(shù)學(xué)是否沒有內(nèi)部矛盾？Godel:

No數(shù)學(xué)是可判定的嗎？能夠找到一種方法，僅僅通過機(jī)械化的計(jì)算，就能判定某個(gè)數(shù)學(xué)陳述是對是錯(cuò)？數(shù)學(xué)證明能否機(jī)械化？Halting

Problem

Hilbert（第二）問題數(shù)學(xué)是完備的嗎？2.3停機(jī)問題是否有無理數(shù)？對角化證明：將所有在［0，1］間的有理數(shù)寫成二進(jìn)制數(shù)，排為一序列：r1,r2,…,rn…構(gòu)造r：r的第i位和ri的第i位不同。結(jié)論：r不可以是有理數(shù)。能否確定一個(gè)圖靈機(jī)會停機(jī)？將圖靈機(jī)排序（按有限態(tài)控制器）：T1,T2,…,Tn,…構(gòu)造T：如果機(jī)器Ti在輸入Ti時(shí)停機(jī)，T在輸入Ti時(shí)不停機(jī)，反之停機(jī)。T停機(jī)與否成為不可判定。2.3停機(jī)問題是否有無理數(shù)？ApplyReductionA不可判定A可reduce到BB也不可判定ApplyReductionA不可判定其他計(jì)算工具其他計(jì)算工具OthercomputationalreductionsMechanic:AnalyticalEnginebyBabbageQuantum:D-WaveonsaleDNAOthercomputationalreductionsAtwoplayergameimplementing“+”Playerone:SixStrategiesInput:Nodes(a,0),(a,1),(b,0)and(b,1)Output:nodes(c,0),(c,1)Playertwo:intermediatenodes(d,0),(d,1)Nontrivialpurestrategypairs:s1=<(a,1),(d,1)>;s2=<(b,1),(d,1)>;s3=<(c,1),(d,0)>;s4=<(c,1),(d,1)>;s5=<(c,0),(d,0)>;PayoffsForPlayerone:onefors4,s5;zerootherwiseForPlayertwo:onefors1,s2,s3;zerootherwise.AtwoplayergameimplementEncodingbyEquilibriumProbabilityX:theprobabilityofplaying(a,1)Y:theprobabilityofplaying(b,1)Z:theprobabilityofplaying(c,1)ForPlayer2:Utilityplaying(d,0):ZUtilityofplaying(d,1):X+YAtequilibriumplayertwohasthesameutilitychoosingitspurestrategies:(d,0)or(d,1)Z=X+YabcdEncodingbyEquilibriumProbabOtheroperationsCanbeimplementedbyatwoplayergameinasimilarmanner.Arithmeticoperations(canbedoneapproximately).+,-,equal_to,assign_C,multiply_by_CComparator:< (mustbedoneapproximately).Logicoperations(exactlydone).∨∧Negation:?OtheroperationsCanbeimplPowerof2PlayerNashItcansolvethefixedpointproblemofapolynomialtimecomputablefunction.Powerof2PlayerNashItca計(jì)算復(fù)雜性計(jì)算復(fù)雜性復(fù)雜性：Pvs.NP問題P：多項(xiàng)式時(shí)間可以計(jì)算的問題NP：多項(xiàng)式時(shí)間可以驗(yàn)證“正確解”的問題復(fù)雜性：Pvs.NP問題P：多項(xiàng)式時(shí)間可以計(jì)算的問題P：多項(xiàng)式時(shí)間可以計(jì)算的問題匹配：給定二部圖，G＝(V1,V2;E),如何找到邊集合的子集M使得V1和V2中的每個(gè)點(diǎn)與E相交一條邊。如學(xué)生申請大學(xué)P：多項(xiàng)式時(shí)間可以計(jì)算的問題匹配：給定二部圖，G＝(V1,VMatchingAlgorithmReductiontoNetworkFlowproblem:thelatterhasapolynomialtimesolution.MatchingAlgorithmReductiontoNP：多項(xiàng)式時(shí)間可以驗(yàn)證“正確解”的問題匹配：給定一圖，G＝(V,E),如何找到邊集合E的子集C形成一個(gè)圈圖，Hamiltonian圈：C經(jīng)過G中每一點(diǎn)恰好一次。見右圖歐拉圈：C經(jīng)過G中每一邊恰好一次。如左圖國王堡七橋問題NP：多項(xiàng)式時(shí)間可以驗(yàn)證“正確解”的問題匹配：給定一圖，G＝NP-Hard？可以在多項(xiàng)式時(shí)間將3SAT問題reduce到Hamiltonain圈3SATisNP-hardSoisHamiltonain圈歐拉圈多項(xiàng)式時(shí)間可解。NP-Hard？可以在多項(xiàng)式時(shí)間應(yīng)用領(lǐng)域應(yīng)用領(lǐng)域這是AI嗎

？"Itismyconvictionthatintentionalphenomenologyhasforthefirsttimemadespiritasspiritthefieldofsystematicscientificexperience,thuseffectingatotaltransformationofthetaskofknowledge.”EdmundHusserl,CrisisofEuropeanHumanity,Pt.II,1935這是AI嗎？"Itismyconvictionth圖靈測試圖靈測試反向圖靈測試反向圖靈測試MachineTranslationMachineTranslationEideticreductionBywhichthephilosophermovesfromtheconsciousnessofindividualandconcreteobjectstothetransempiricalrealmofpureessencesandthusachievesanintuitionoftheeidos(Greek:“shape”)ofathing—i.e.,ofwhatitisinitsinvariableandessentialstructure,apartfromallthatiscontingentoraccidentaltoit.FromEncyclopeadiaBritannicaEideticreductionBywhichtheTheArtofComputerProgrammingFundamentalAlgorithmsSeminumericalAlgorithmsSortingandSearchingCombinatorialAlgorithmsByD.KunthTheArtofComputerProgramminDeepLearningDeepLearningWhatdoesbigdatabringus?邏輯關(guān)系？Wisdomofthecrowd？Networkanalysis?Whatdoesbigdatabringus?邏輯LifeasitcouldbeTheinventionofthecomputerhasrevolutionizedscience.Withrespecttofindingtheessentialstructuresoflife,forexample,ithasenabledscientistsnotonlytoinvestigateempiricalexamples,butalsotocreateandstudynovelhypotheticalvariationsbymeansofsimulation:‘lifeasitcouldbe’.TomFroese&ShaunGallagher(2010).PhenomenologyandArtificialLife:TowardaTechnologicalSupplementationofPhenomenologicalMethodology.

HusserlStudies26(2):83-106.LifeasitcouldbeTheinventiMoneyasitcouldbeMoneyasitcouldbe2024/3/3136StonemoneyInYapisland,called‘fei’

MadeofparticularvarietyandqualityoflimestoneTransferable.OwnershipPublicRecognizedSource:2024/3/3136StonemoneyInYapi2024/3/3137SupportactivitiesovertheInternet.RoleofE-Money2024/3/3137Supportactivities2024/3/3138Aimtorecreatetheconceptofcash-basedshoppingovertheInternet.UsecryptographictechniquesandprotocolsNewthinking.DesignofaInternetFinancialMarket:Bitcoin2024/3/3138Aimtorecreatethe2024/3/3139OutlineBitcoinOriginoffunds:Outofthinair(無中生有)BitcoinMining:Anyonecanjointheefforttominenewbitcoins.Theprotocolispresetandagreedbyallwhoparticipate,enforcedbycomputationalcomplexity.Internetcommercialactivitiesareeasilysupported.2024/3/3139OutlineBitcoinOrigTheBitcoinDesignTheBitcoinDesign2024/3/3141Recordalltransactionsandmovesof

money每一筆交易被紀(jì)錄下來。最初的交易由創(chuàng)始人發(fā)行bitcoin促成。Bitcoin由交易轉(zhuǎn)換它的擁有者。每個(gè)人擁有的Bitcoin是社區(qū)的commonknowledge。對比Fei：almostthesame.2024/3/3141Recordalltransact202