《俄罗斯》P初中地理人教

Reductions邓小铁上海交通大学Reductions邓小铁计算机科学的Reduction计算机科学的Reduction（vonNeuman的电脑ENIAC）（vonNeuman的电脑ENIAC）计算机科学计算机科学计算机应用计算机应用逻辑电子元件逻辑电子元件逻辑电子线路用AND-OR-NOT元件组合的线路Universal：可以计算任何（变量有限）的逻辑函数应用领域自动机计算机，空调，电梯，洗衣机，电视，手机，GPS导航，电子游戏，以及许多我们今天已经难以离开的现代电子科技产品。逻辑电子线路用AND-OR-NOT元件组合的线路可计算性理论可计算性理论可计算性理论图灵机有限态控制器：状态集合，字母集合，转移规则输入／输出纸带等价计算体系递归函数λ演算可计算性理论图灵机Hilbert（第二）问题数学是完备的吗？

面对那些正确的数学陈述，我们是否总能找出一个证明？数学真理是否总能被证明？Godel:

No数学是一致的吗？数学是否前后一致，不会得出某个数学陈述又对又不对的结论？数学是否没有内部矛盾？Godel:

No数学是可判定的吗？能够找到一种方法，仅仅通过机械化的计算，就能判定某个数学陈述是对是错？数学证明能否机械化？Halting

Problem

Hilbert（第二）问题数学是完备的吗？2.3停机问题是否有无理数？对角化证明：将所有在［0，1］间的有理数写成二进制数，排为一序列：r1,r2,…,rn…构造r：r的第i位和ri的第i位不同。结论：r不可以是有理数。能否确定一个图灵机会停机？将图灵机排序（按有限态控制器）：T1,T2,…,Tn,…构造T：如果机器Ti在输入Ti时停机，T在输入Ti时不停机，反之停机。T停机与否成为不可判定。2.3停机问题是否有无理数？ApplyReductionA不可判定A可reduce到BB也不可判定ApplyReductionA不可判定其他计算工具其他计算工具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计算复杂性计算复杂性复杂性：Pvs.NP问题P：多项式时间可以计算的问题NP：多项式时间可以验证“正确解”的问题复杂性：Pvs.NP问题P：多项式时间可以计算的问题P：多项式时间可以计算的问题匹配：给定二部图，G＝(V1,V2;E),如何找到边集合的子集M使得V1和V2中的每个点与E相交一条边。如学生申请大学P：多项式时间可以计算的问题匹配：给定二部图，G＝(V1,VMatchingAlgorithmReductiontoNetworkFlowproblem:thelatterhasapolynomialtimesolution.MatchingAlgorithmReductiontoNP：多项式时间可以验证“正确解”的问题匹配：给定一图，G＝(V,E),如何找到边集合E的子集C形成一个圈图，Hamiltonian圈：C经过G中每一点恰好一次。见右图欧拉圈：C经过G中每一边恰好一次。如左图国王堡七桥问题NP：多项式时间可以验证“正确解”的问题匹配：给定一图，G＝NP-Hard？可以在多项式时间将3SAT问题reduce到Hamiltonain圈3SATisNP-hardSoisHamiltonain圈欧拉圈多项式时间可解。NP-Hard？可以在多项式时间应用领域应用领域这是AI吗

？"Itismyconvictionthatintentionalphenomenologyhasforthefirsttimemadespiritasspiritthefieldofsystematicscientificexperience,thuseffectingatotaltransformationofthetaskofknowledge.”EdmundHusserl,CrisisofEuropeanHumanity,Pt.II,1935这是AI吗？"Itismyconvictionth图灵测试图灵测试反向图灵测试反向图灵测试MachineTranslationMachineTranslationEideticreductionBywhichthephilosophermovesfromtheconsciousnessofindividualandconcreteobjectstothetransempiricalrealmofpureessencesandthusachievesanintuitionoftheeidos(Greek:“shape”)ofathing—i.e.,ofwhatitisinitsinvariableandessentialstructure,apartfromallthatiscontingentoraccidentaltoit.FromEncyclopeadiaBritannicaEideticreductionBywhichtheTheArtofComputerProgrammingFundamentalAlgorithmsSeminumericalAlgorithmsSortingandSearchingCombinatorialAlgorithmsByD.KunthTheArtofComputerProgramminDeepLearningDeepLearningWhatdoesbigdatabringus?逻辑关系？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每一笔交易被纪录下来。最初的交易由创始人发行bitcoin促成。Bitcoin由交易转换它的拥有者。每个人拥有的Bitcoin是社区的commonknowledge。对比Fei：almostthesame.2024/3/3141Recordalltransact202