可判定性

✍ dations ◷ 2025-05-15 15:02:38 #可判定性
一个语言 L {displaystyle L} ,是一个集合,且其补集为 L ¯ {displaystyle {overline {L}}} 。 当 L {displaystyle L} 是图灵机可识别时,语言 L {displaystyle L} 则称为半可判定。 当语言 L {displaystyle L} 不是图灵机可识别,则为不可判定语言。 当且仅当 L {displaystyle L} 和 L ¯ {displaystyle {bar {L}}} 都是图灵机可识别的时候,L才能称为可判定语言。指一个询问真 / 假的问题是否可被回答。若不论一个问题答案为真或为假时均能得出该答案,则称这个问题、或解决该问题时所用的算法为可判定的;若只能在答案为真时得出、但在答案为假时不能做出判断,那么称为半可判定的;若根本不能得出为真或为假的结论,那么称为不可判定的。

相关

  • 词位词位(英语:lexeme)是决定词义的基本抽象单位,构成一组通过屈折变化相联系的词语的基础。 词位也是词法学分析中,指代相同词根、不同形式的一组单词的单位。词元(英语:Lemma (morpho
  • 花生花生过敏(Peanut allergy)是对花生的食物过敏,和树坚果过敏不同。身体的过敏症状包括痒、荨麻疹、血管性水肿、皮肤炎、流鼻涕、哮喘、腹痛、低血压、腹泻,也可能会心搏停止。可
  • 西班牙语西班牙语是美国继英语之后第二大广泛使用的语言。在美国,西班牙语使用者的人数比汉语、法语、意大利语、夏威夷语以及美洲原住民语言的使用人数的总和还要多。根据2009年由美
  • 生物大分子生物大分子指的是作为生物体内主要活性成分的各种分子量达到上万或更多的有机分子。常见的生物大分子包括蛋白质、核酸 (DNA、RNA等)、糖类。这只是一个概念性定义,与生物大
  • 系膜细胞肾小球内系膜细胞(Intraglomerular mesangial cells)是位于肾的肾小体内间的肾小球微血管的特别周皮细胞(pericyte/周细胞)。系膜细胞是单核细胞或平滑肌的来源,典型地覆盖30%的
  • 分泌物黏液(英语:mucus)是一种从人体的黏膜内层分泌出来的湿滑液体。黏液一般都是比较浓稠的胶状体,含有具抗菌功效的酵素,例如:溶菌酶、抗体等。黏液由满布黏膜表面内的杯状细胞制造,由
  • 米兰-利纳特机场米兰-利纳特机场(意大利语:Aeroporto di Milano-Linate,IATA代码:LIN;ICAO代码:LIML)是意大利米兰三大机场之一。主要用于国内和短途国际航班(所有国际航班的目的地仅限于欧洲境内),至
  • 工具书工具书指一种在学习中和工作中可以作为工具使用的特定类型的书籍,专供查考资料,以解决工作或学习过程中所遇到的某些疑难问题。这些书籍经过汇集、编著或译述的资料,把相关领域
  • 直立人直立人又称直立猿人,其生存年代为更新世早期至中期。直立人已经能够直立行走并且制造石器,是旧石器时代早期的人类。北京猿人、蓝田人、元谋人、巫山人、澎湖原人等都属于直立
  • 粗衬线体在字体排印学中,粗衬线体(或称埃及体)是一种衬线字体,其衬线是更粗、块状的。 衬线终端可以是钝头和棱角(Rockwell),或圆角(Courier)。粗衬线体发明于十九世纪,在十九世纪也最为流行。