计算机科学哲学（二）
后一个问题与更普遍的问题有关，即确定工件如何具有功能，以及结构属性与代理意图相关意味着什么。这一问题在生物哲学和认知科学中也很常见，目前已提出了两种主要理论作为解决方案。根据因果功能理论（Cummins 1975），功能由制品的物理能力决定：例如，心脏收缩和扩张的物理能力决定了它在循环系统中泵血的功能。然而，当该理论应用于技术制品时，它面临着严重的问题。首先，它阻碍了正确性和故障的定义（Kroes 2010）：假设安装在我们智能手机上的呼叫过滤应用程序开始禁止来自我们手机通讯录中联系人的呼叫，根据因果功能理论，这将是该应用程序的一项新功能。其次，该理论没有区分预期功能和副作用（Turner 2011）：如果通话时间较长，我们的智能手机肯定会开始发热，但这不是客户或开发人员预期的功能。按照意向功能理论（McLaughlin 2001，Searle 1995），设计者或用户所确定的功能就是人工制品的预期功能，而人工制品的结构属性则是经过选择以便能够实现它。该理论能够解释正确性和故障性，也能区分副作用和预期功能。然而，它并没有说明功能实际上存在于何处，是在人工制品中还是在代理的头脑中。在前一种情况下，我们又回到了人工制品如何具备功能的问题上。在后一种情况下，需要进一步解释心理状态与人工制品的物理属性之间的关系（Kroes 2010）。Turner（2018）认为因果功能理论和意向功能理论背后的直觉对于理解计算系统中功能和结构的关系都很有用，并建议将这两种理论合并为一个理论。一方面，没有实现就没有功能；另一方面，没有客户、开发人员和用户就没有意图。
自然计算系统也可以保持类似的立场。根据因果理论，功能是由结构层面引起的，似乎没有预期或指定的功能。然而，自然计算系统的特点是多重可指定性：物理或生物结构可以实现不同的功能，即它可以以多种方式指定（Fresco 等人，2021 年）。一个简单的例子是实现布尔连词或布尔包含析取的门，这取决于哪些电压范围被解释为真和假，或标记为真和假。因此，虽然系统计算的函数仍然不确定，但代理选择的标记方案会修复它（Curtis-Trudel，2022 年）。
3. 算法
尽管自古以来就为人所知并被广泛使用，但定义算法的问题仍然存在（Vardi，2012 年）。 “算法”一词源于 9 世纪波斯数学家 Abū Jaʿfar Muḥammad ibn Mūsā al-Khwārizmī 的名字，他使用阿拉伯数字制定了算术运算规则。事实上，计算乘法或除法等基本算术运算所遵循的规则就是算法的日常例子。其他众所周知的例子包括使用圆规和直尺平分角的规则，或计算最大公约数的欧几里得算法。直观地说，算法是一组允许完成给定任务的指令。尽管数学有着这一古老传统，但只有现代逻辑和哲学反思才提出了定义算法的任务，这与 20 世纪初数学的基础危机有关（参见数学哲学条目）。有效可计算性的概念源自逻辑研究，为直观的算法概念提供了某种形式上的对应，并催生了计算理论。从那时起，人们提出了不同的算法定义，从形式化方法到非形式化方法，如下一节所述。
3.1 经典方法
Markov (1954) 首次精确定义了算法，即确定、适用且有效的计算过程。如果所涉及的指令足够精确，不允许在执行过程中出现任何“任意选择”，则计算过程是确定的。（人类或人工智能）计算机绝不能不确定下一步要执行什么步骤。算法适用于 Markov，因为它们适用于输入类别（基本算术运算的自然数），而不是单个输入（特定自然数）。Markov (1954:1) 将有效性定义为“算法获得特定结果的趋势”。换句话说，算法是有效的，因为它最终会产生计算问题的答案。
Kleene (1967) 将有限性指定为另一个重要属性：算法是一种可以通过一组有限的指令来描述的过程，需要有限数量的步骤来提供计算问题的答案。作为反例，考虑一个由有限数量的步骤定义的 while 循环，但由于循环中的条件始终得到满足，因此该循环将永远运行。指令还应适合机械执行，即机器无需任何洞察力即可遵循它们。遵循马尔可夫的可确定性和强化有效性，Kleene (1967) 还指定指令应该能够识别计算问题的解决方案已经实现，并停止计算。
Knuth (1973) 回顾并深化了 Markov (1954) 和 Kleene (1967) 的分析，并指出：
除了仅仅是一组有限的规则，为解决特定类型的问题提供一系列操作之外，算法还有五个重要特征：
有限性。 在有限数量的步数之后，算法必须始终终止。 [...]
确定性。 必须精确定义算法的每个步骤; 必须严格和明确地指定要执行的行动。 [...]
输入。 算法具有零或多个输入。 [...]
输出。 算法具有零或多个输出。 [...]
有效性。 通常，算法通常是有效的，因为它的操作必须是足够的基本，即它们原则上可以完全完成，并且在使用铅笔和纸的某人的有限时间。 （Knuth 1973：4-6）[...]
与Kleene（1967）一样，有限性影响指令的数量和实现的计算步骤的数量。 与马尔可夫的决定性一样，Knuth的明确原理要求每次连续计算步骤明确指定。 此外，Knuth（1973）更明确地要求算法具有（潜在的空集）输入和输出。 通过没有输入或输出Knuth的算法可能是指使用内部存储数据的算法作为未将数据返回到外部用户的输入或算法（RapaPort 2023，CH.7）。 对于有效性，除了马尔可夫的趋势“获得某个结果”之外，Knuth要求在有限的时间内获得结果，并且指令是原子的，即，简单地是人工或人造计算机可以理解和可执行的。
3.2正式方法
Gurevich（2011）一方面维护，即不可能提供算法的正式定义，因为概念随着时间的推移继续发展：考虑如何在古代数学中使用的顺序算法是平行的，模拟或当前计算机科学实践中的量子算法，以及如何在不久的将来设想新的算法。 另一方面，如果仅使用经典顺序算法，则可以先进的正式分析。 特别是，Gurevich（2000）提供了这类算法的公理定义。
可以通过满足三个公理的顺序抽象状态机模拟任何顺序算法：
顺序时间假期与任何算法的关联A联系人是一组状态S（a），一组初始状态I（a）s（a）子集的s（a），以及来自A.状态的一步变换的S（a）到s（a）的映射为snapsthot运行算法的描述。 从一些初始状态开始，A的r是（潜在的无限）序列的状态，使得在序列中存在从一个状态到其继承者的一步变换。 终止未被Gurevich定义预设。 一步变换不需要是原子的，但它们可以由一组有界原子操作组成。
根据抽象州假设，S（a）中的各国是一流的结构，通常在数学逻辑中定义; 换句话说，状态为一阶陈述提供了一个语义。
最后，界限探索假设了一个给定的两个状态x和y总是一个术语，这样，当x和y重合t时，x的一组更新对应于y x和y的一组更新，而每T中的术语T在X中的评估与Y中的T的评估相同。这允许算法A仅探索与T的术语相对术语的各个部分。
MoSchovakis（2001）对象，算法直观概念未充分捕获抽象机器。 给定一般递归函数F：ℕ→ℕ在自然数上定义，通常有许多不同的算法计算它; “必需的，实现独立的属性”不是由抽象机器捕获的，而是由递归方程的系统捕获。 考虑分拣列表的算法合并; 合并有许多不同的抽象机器，并且出现了哪一个作为合并算法选择哪一个。 合并算法代替指定所涉及的功能的递归方程式，而合并程序的抽象机器是相同算法的不同实现。 Moschovakis的正式分析提出了两个问题：相同算法的不同实现应该是等效的实现，但是，算法实现之间的等价关系将被正式定义。 此外，它仍然阐明了递归方程系统正式的算法的直观概念量。
Primiero（2020）建议在三种不同水平的抽象中读取算法的性质。 在一个非常高的LOA中，可以从他们描述的过程中定义算法，允许许多不同的状态和转换集。 在该LOA算法可以被理解为非正式规范，即作为过程P的非正式描述。在较低的LOA下，算法指定解决给定计算问题所需的指令; 换句话说，它们指定了一个过程。 因此，可以将算法定义为过程中的某些给定的形式语言L的过程，或者如何执行过程P.算法的许多重要属性，包括与复杂性类和数据结构相关的那些，而不是在过程LOA中确定，而是参考抽象机器实施程序是必需的。 在底部LOA，算法可以定义为可实现的抽象机，viz。 作为规范，以形式的语言L为给定的抽象机器M的程序P的执行。算法的三倍定义允许Primiero（2020）在代数概念方面向算法提供算法的正式定义模拟和分配（Milner 1973，参见Angius和Primero 2018）。 执行程序PI的机器MI实现了执行程序PJ的机器MJ的相同算法，如果且仅当抽象机器解释MI和MJ处于双刺激关系时才。
3.3非正式方法
Vardi（2012）强调如何，尽管有许多正式和非正式定义，但没有关于算法的一般性共识。 Gurevich（2000）和MoSchovakis（2001）的方法可以被证明是逻辑上等同的，只为算法提供逻辑结构，揭示未解答的主要问题。 Hill（2013）表明，算法的非正式定义，考虑到一个关于算法的直观理解，可能更有用，特别是对于公众话语和从业者和用户之间的沟通。
Rapaport（2012年，附录）旨在总结上面速写的算法的三个经典定义，说明：
一种算法（用于执行目标g的执行器e）是：
一个过程，即陈述的有限组（或序列）（或规则或指令），例如每个语句是：
由来自有限字母表的有限数量的符号（或标记）组成
和e-c的毫不含糊，
e知道如何做到这一点
e可以做到这一点
它可以在有限的时间内完成
并且，在做完之后，e知道下一步做什么 -
哪个程序采用有限的时间（即它停止），
这与G完成了。
RapaPort强调算法是一种过程，即采取规则或指示的形式的有限陈述。 以下是通过要求指令包含来自有限字母表的有限数量的符号来表达联合。
Hill（2016）旨在提供从Rapaport的算法的非正式定义（2012）：
算法是有限，摘要，有效的化合物控制结构，必要，在给定的规定下完成给定的目的。（山2016：48）。
首先，算法是复合结构而不是原子对象，即，它们由较小的单位组成，即计算步骤。 这些结构是有限且有效的，如Markov，Kleene和Knuth明确提及。 虽然这些作者没有明确提及抽象，但山丘（2016）保持在分析中是隐含的。 算法简单地是摘要，因为它们缺乏时空属性，并且与他们的实例无关。 它们提供控制，即“将某种状态从一个状态转到另一个状态的内容，表达在变量的值和随后的动作中表示（第45页）。 算法是必需的，因为它们命令态转换来执行指定的操作。 最后，算法运作以在某些通常规定的规定或前提条件下实现某些目的。 从这个观点来看，作者争辩，算法是在他们指定某些资源下指定目标的规范的标准条例。 该定义允许区分从其他化合物控制结构的算法。 例如，食谱不是算法，因为它们无效; 不是游戏，这不是必不可少的。
4.计划
计算机程序的本体论与计算系统的归入性质严格相关（见§1）。 如果基于软件硬件二分法定义计算系统，则程序是解释前者并反对硬件的具体性质的抽象实体。 这些解释的示例是在§1.1中提供的，并包括Colburn（2000）的“具体抽象”定义，Irmak（2012年）的“抽象工件”表征，以及Duncan（2011）提出的机器的规范。 相比之下，根据LOA的层次结构的计算系统的解释，程序是算法的实现。 我们参考§5实施方案本体的实施。 本节重点介绍了文献中具有重要相关性的计划的定义，即将计划作为理论或文物视为理论或作为文物的观点，重点关注计划与世界之间关系的问题。
4.1 程序作为理论
程序是理论的观点可以追溯到认知科学的方法。在所谓的信息处理心理学 (IPP) 的背景下，为了模拟人类认知过程，Newell 和 Simon (1972) 提出了模拟程序是其模拟系统的经验理论的论点。Newell 和 Simon 为计算机程序分配了模拟系统和模拟系统（即运行程序的机器）理论的角色，以对模拟系统进行预测。具体来说，给定一个要解决的特定问题，模拟程序的执行轨迹可用于预测人类受试者在被要求完成相同任务时将执行的心理操作策略。如果执行轨迹与人类受试者的操作策略的口头报告不匹配，则模拟程序提供的经验理论将被修改。根据 Newell 和 Simon 的说法，这种计算机程序的预测用途可与通过微分或差分方程表达的系统演化定律的预测用途相媲美。
Newell 和 Simon 认为程序是理论，认知科学家 Pylyshyn (1984) 和 Johnson-Laird (1988) 也认同这一观点。两人都认为，与典型的理论相比，程序更善于应对要建模的模拟过程的复杂性，迫使人们填写执行程序所需的所有细节。虽然在科学研究的某个阶段可能会提出不完整或不连贯的理论，但程序并非如此。
另一方面，Moor (1978) 认为程序即理论论题是计算机科学的另一个神话。由于程序只能模拟一些经验现象，因此它们最多只能充当这些现象的计算模型。 Moor 注意到，要将程序视为模型，仍然需要语义函数来解释所模拟的经验系统。但是，程序是模型的观点不应被误认为是程序作为理论的定义：理论解释和预测模型模拟的经验现象，而程序模拟则不能提供这种解释和预测。
根据计算机科学家 Paul Thagard (1984) 的说法，将程序理解为理论需要从句法或语义的角度来看待理论（参见科学理论的结构条目）。但程序不符合这两种观点。根据句法观点（Carnap 1966，Hempel 1970），理论是用某种定义的语言表达的句子集，能够描述目标经验系统；其中一些句子定义了理论的公理，一些是表达这些系统规律的类似定律的陈述。程序是用某种定义的编程语言编写的指令集，但它们并不描述任何系统，因为它们是过程语言实体而不是声明性语言实体。对此，Rapaport (2023) 反对说，过程编程语言通常可以翻译成声明性语言，并且有些语言（例如 Prolog）既可以过程化解释，也可以声明化解释。根据语义观点（Suppe 1989，Van Fraassen 1980），理论是由一组模型引入的，这些模型定义为满足理论句子的集合论结构。然而，与 Moor (1978) 不同，Thagard (1984) 否认程序具有模型的认识论地位：程序模拟物理系统而不满足理论的定律和公理。相反，出于模拟目的，程序包括所用编程语言的实现细节，但不包含被模拟的目标系统的实现细节。
计算机科学家 Peter Naur (1985) 对程序是否是理论的问题提出了另一种不同的方法。根据 Naur 的说法，编程是一个理论构建过程，并不是说程序是理论，而是因为成功的程序的开发和生命周期要求程序员和开发人员掌握程序理论。根据 Ryle (2009) 的说法，理论在这里被理解为科学界共享的关于一些经验现象的知识集合，不一定以公理或形式表达。程序理论在程序生命周期中是必要的，以便能够根据观察到的错误计算或对程序被要求解决的计算问题的不满意解决方案来管理程序修改请求。特别是，程序理论应该允许开发人员修改程序，以便为相关问题提供新的解决方案。因此，Naur (1985) 认为，在软件开发中，这些理论比文档和规范更为重要。
对于 Turner (2010, 2018 ch. 10) 来说，编程语言是由形式语法和形式语义定义的数学对象。具体来说，每个句法结构（例如赋值、条件或 while 循环）都由确定其语法的语法规则和将含义与其关联的语义规则定义。根据是首选操作语义还是指称语义，含义分别根据抽象机器的操作或从一组状态到一组状态的数学部分函数来给出。例如，在操作语义下，简单赋值语句
x
:=
E
�
:=
�
与机器操作
u
p
d
a
t
e
(
s
,
x
,
v
)
�
(
�
,
�
,
�
)
相关联，该操作将变量
v
�
（解释为
E
�
）分配给处于
s
�
状态的变量
x
�
。无论是在操作语义还是在指称语义的情况下，程序都可以理解为表达实现机器操作的数学理论。考虑操作语义：形式为
⟨
P
,
s
⟩
⇓
s
′
⟨
�
,
�
⟩
⇓
�
′
的句法规则在语义上表明，在状态
s
�
下执行的程序
P
�
导致
s
′
.
�
′
.
根据 Turner (2010, 2018) 的说法，具有操作语义的编程语言类似于公理运算理论，其中规则为关系
⇓
⇓
提供公理。
4.2 程序作为技术工件
程序可以被理解为技术工件，因为编程语言和任何其他工件一样，都是基于功能和结构属性来定义的（Turner 2014, 2018 ch. 5）。 （高级）编程语言的功能属性由与语言的每个句法结构相关的语义提供。Turner（2014）指出，只有当编程语言的功能级别被隔离时，才能真正将其理解为公理理论。另一方面，结构属性是根据语言的实现来指定的，但与计算机的物理组件无关：给定一个具有相关功能描述的语言句法结构，其结构属性由机器为实现手头构造的指令而执行的物理操作决定。例如，赋值构造
x
:=
E
�
:=
�
将与表达式
E
�
的值的物理计算以及
E
�
的值在物理位置
x
�
中的放置相关联。
将编程语言视为技术工件的另一个要求是，它必须具有为语言实现提供正确性标准的语义。程序员通过语义来证明程序的功能和结构属性，以对程序拥有正确性管辖权。
