|
据 北 美 消 息， 美 国 科 学 家 利 用 简 单 的 DNA 计 算 机， 在 实 验 中 为 一 个 有 24 个 变 量、 100 万 种 可 能 结 果 的 数 学 难 题 找 到 了 答 案。 这 是 迄 今 利 用 非 电 子 化 计 算 手 段 解 出 的 最 复 杂 数 学 问 题， 表 明 DNA 计 算 机 研 制 又 迈 出 了 重 要 一 步。
美 国 南 加 利 福 尼 亚 大 学 教 授 阿 德 勒 曼 将 这 一 研 究 成 果 发 表 在 新 一 期 美 国 《科 学》 杂 志 上。
DNA (脱 氧 核 糖 核 酸) 是 生 物 遗 传 的 物 质 基 础， 它 通 过 4 种 核 苷 酸 的 排 列 组 合 存 储 生 物 遗 传 信 息。 将 运 算 信 息 排 列 于 DNA 上， 并 通 过 特 定 DNA 片 段 之 间 的 相 互 作 用 来 得 出 运 算 结 果， 是 DNA 计 算 机 工 作 的 主 要 原 理。
阿 德 勒 曼 教 授 是 DNA 计 算 机 研 究 领 域 的 先 驱。 他 于 1994 年 在 实 验 中 演 示， DNA 计 算 机 可 以 解 决 著 名 的 "推 销 员 问 题"， 首 次 论 证 了 这 种 计 算 技 术 的 可 行 性。 "推 销 员 问 题" 用 数 学 语 言 来 说， 是 要 求 在 7 个 城 市 间 寻 找 最 短 的 路 线， 这 一 问 题 相 对 简 单， 心 算 就 可 以 给 出 答 案。
但 这 次 阿 德 勒 曼 教 授 用 DNA 计 算 机 演 示 新 问 题 难 度 就 大 多 了， 靠 人 脑 的 计 算 能 力 基 本 无 法 处 理。 这 一 逻 辑 问 题 名 叫 "NP 完 全 3-SAT 问 题"， 听 起 来 不 知 所 云， 但 可 以 形 象 化 地 表 述 如 下：
假 设 你 走 进 一 个 有 100 万 辆 汽 车 的 车 行， 想 买 一 辆 称 心 的 车。 你 向 销 售 员 提 出 了 一 大 堆 条 件， 如 "想 买 一 辆 ４ 座 和 自 动 档 的"， "敞 蓬 和 天 蓝 色 的" 宝 马 车 等 等， 加 起 来 多 达 24 项。 在 整 个 车 行 中， 能 满 足 你 所 有 条 件 的 车 只 有 一 辆。 从 理 论 上 说， 销 售 员 必 须 一 辆 辆 费 劲 地 找。 传 统 的 电 子 计 算 机 采 用 的 就 是 这 种 串 行 计 算 的 办 法 来 求 解。
阿 德 勒 曼 等 设 计 的 DNA 计 算 机 则 对 这 一 问 题 进 行 了 并 行 处 理。 他 们 首 先 利 用 DNA 片 段 编 码 了 100 万 种 可 能 的 答 案， 然 后 将 其 逐 一 通 过 不 同 容 器， 每 个 容 器 都 放 入 了 代 表 24 个 限 制 条 件 之 一 的 DNA。 每 通 过 一 个 容 器， 满 足 特 定 限 制 条 件 的 DNA 分 子 经 反 应 后 被 留 下， 并 进 入 下 一 个 容 器 继 续 接 受 其 它 限 制 条 件 的 检 验， 不 满 足 的 则 被 排 除 出 去， 从 解 决 这 个 问 题 的 过 程 中 可 以 看 出， 理 论 上， DNA 计 算 机 的 运 算 策 略 和 速 度 将 优 于 传 统 的 电 子 计 算 机。 阿 德 勒 曼 教 授 说， 虽 然 他 们 的 新 实 验 进 一 步 提 高 了 DNA 计 算 机 模 型 的 运 算 能 力， 但 总 的 来 说， DNA 计 算 机 错 误 率 还 是 太 高； 要 真 正 超 越 电 子 计 算 机， 还 需 要 在 DNA 大 分 子 操 纵 技 术 等 方 面 有 大 的 突 破。
|
