标签: decidable

我编写了一些需要-XUndecidableInstances来编译的Haskell代码.我确实理解为什么会发生这种情况,因为存在某种违反的条件,因此GHC会大喊大叫.

但是,我从来没有遇到类型检查器实际上挂起或在无限循环中结束的情况.

非终止实例定义是什么样的 - 你能给出一个例子吗？

我正在使用Mozilla的Javascript教程,我来了解这条信息.

高级语言嵌入了一个名为"垃圾收集器"的软件,其工作是跟踪内存分配和使用,以便找到不再需要分配内存的时间,在这种情况下,它将自动释放它.该过程是近似的,因为知道是否需要某些存储器的一般问题是不可判定的(不能通过算法解决).

我熟悉不可判断性和垃圾收集器的概念,但我似乎无法理解为什么这是一个不可判定的问题？

对于不可判断的问题和NP难题之间的关系,我有点困惑.NP难题是否是不可判定问题的一个子集,或者它们是否相同且相同,还是它们不具有可比性？

对我而言,我一直在与朋友争辩说,不可判断的问题是NP难题的超集.存在一些不是NP难以解决的问题但是不可判定的问题.但我发现这个论点很弱,而且有点困惑.是否存在不完全的NP完全问题.在NP hard中有任何问题是可判定的吗？

一些讨论会有很大的帮助!谢谢!

我使用这种类型来推断可以执行可解析解析的字符串:

data Every : (a -> Type) -> List a -> Type where
  Nil : {P : a -> Type} -> Every P []
  (::) : {P : a -> Type} -> P x -> Every P xs -> Every P (x::xs)

例如,定义数字[0-9],如下所示:

data Digit : Char -> Type where
  Zero  : Digit '0'
  One   : Digit '1'
  Two   : Digit '2'
  Three : Digit '3'
  Four  : Digit '4'
  Five  : Digit '5'
  Six   : Digit '6'
  Seven : …

在计算理论中,可证明和可判断的术语是可互换的吗？他们的意思是一样的吗？

例如,您经常会看到一个问题是否可证明是一个决策问题(Das Entscheidungsproblem).

我想创建一个名为Linear的Num超类

class Linear a where 
  add :: a -> a -> a

instance (Num a) => Linear a where
  add = (+)

我收到错误:

Illegal instance declaration for `Linear a'
  (All instance types must be of the form (T a1 ... an)
   where a1 ... an are *distinct type variables*,
   and each type variable appears at most once in the instance head.
   Use -XFlexibleInstances if you want to disable this.)
In the instance declaration for `Linear a'

根据我的理解,关于这条线的事情instance (Num a) …

我一直在寻找为什么OWL Full无法确定的原因，但是我还没有找到一个易于理解的示例来使我理解它。

我发现有陈述解释这是由于“封闭性”引起的，并且还与OWL Full可以同时具有作为属性的类和也作为个人的类这一事实有关。

但是我不理解这些陈述之间的关系。

我不明白为什么没有标记接受状态时Turing Machine T，ACCEPTS并在标记接受状态时为什么拒绝：

E（dfa）= {| A是DFA，L（A）=空集（没有符号）}

E（dfa）是一种可决定的语言。

证明：DFA可以接受一些字符串，当从起始状态到达接受状态时，可以通过>沿DFA的箭头进行移动来实现。为了测试这种情况，我们可以设计一个> TM T，它使用类似于示例3.23的标记算法。

T =“在input上，其中A为DFA：1.标记A的开始状态。2.重复直到未标记任何新状态：3.标记从已标记的任何状态进入转换的任何状态4.如果没有标记接受状态，则接受；否则，拒绝。”

在我看来，这是倒退的。谁能解释一下？

谢谢。

这是我的第一篇文章,如果我犯了错误就道歉.

我怀疑,在Coq中,像Stream这样的共同类型没有可判定的平等.也就是说,给定两个流s和t,不可能识别s = t或〜(s = t).我怀疑Coq中的所有共同类型都是如此.

快速谷歌和搜索堆栈交换不会透露任何确认.谁能证实这一点或纠正我？

如果L1和L2是语言,我们有一种新语言

INTERLACE(L1, L2) = {w1v1w2v2 . . . wnvn | w1w2 . . . wn ? L1, v1v2 . . . vn ? L2}.

例如,if abc ? L1和123 ? L2thena1b2c3 ? INTERLACE(L1, L2)

我怎样才能证明INTERLACE:

1. 可判定的？
2. 可识别？

我知道如何显示这种语言是正常的.对于可判定的我不太确定..

这就是我的想法:

为了表明在操作中关闭可判定语言的类INTERLACE需要表明如果A和B是两种可判定的语言,那么有方法可以找到INTERLACE语言是否可判定.假设A,B可判定语言M1,M22 TM谁决定,分别.

在我想我必须说如何构建识别语言的DFA之后？