腾讯云

文章/答案/技术大牛

发布

社区首页 >问答首页 >递归可枚举(可计算可枚举)语言在排列下关闭？

问递归可枚举(可计算可枚举)语言在排列下关闭？
EN

Stack Overflow用户

提问于 2014-12-14 12:17:44

回答 1查看 366关注 0票数 1

如果L是一种语言。语言perms( L )是所有来自L的单词排列的语言。

真或假：如果L是递归可枚举的(可计算枚举的)，那么perms(L)也是递归枚举的。

这是在之前的期末考试中，还有一个问题:如果L是可判定的，那么perms(L)也是如此，我认为这是正确的。

我想我会说是假的，但我没有证据支持这一说法。

computability

decidable

回答 1

Stack Overflow用户

发布于 2015-08-11 07:18:17

想一想“递归枚举”是什么意思。这意味着您可以定义一个TM，它将用该语言编写每个字符串。如果给TM足够的时间，它最终会写出任何给定的字符串。

对于语言中任何给定的字符串，它都有有限的排列。给定字符串，图灵机器当然可以写出字符串的所有排列。

想象一下将这两台图灵机器放在一起:第一台枚举语言中的所有字符串，第二台发出这些字符串的所有排列。结果是第一语言中所有字符串排列的枚举。

上述图灵机的结合导致了一种新的图灵机。因此，我们有一个图灵机，它以所需的语言枚举所有字符串。根据定义，这种语言是递归枚举的。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/27473602

复制

算法：递归实现排列型枚举

int static 递归内存算法

小颜同学

2023/08/24

1830

递归实现Ann全排列的枚举(基于Python)

官方文档 python 编程算法

在写一些概率统计题的模拟时，经常需要把A(n,n)、C(n,m)的排列组合全部列出来，这里记录一下A(n,n)全排列全部遍历的实现。根据概率论中的排列组合知识知道A(n,n)=n!=n*(n-1)…*1；最终结果的数量一共有n的阶乘，例如对于集合{1,2,3},有6种全排列。

蛰虫始航

2019/09/28

1.3K0

递归实现指数型，排列型，组合型枚举

编程算法

按照上面代码开始的时候stu[1] = 2,表示的是不选，就是最左边那条路径，然后dfs[u+1] ，此时u + 1 = 2,相当于在第二层，然后st[2] = 2,表示第二层仍然不选，，再次有dfs[u+1],此时dfs里面u = 3了， 3 > 2,这样在这个dfs嵌套里面，可以打印了，就有由于此时 stu[1] = 2,stu[2] = 2,都不打印，这样，退出这个dfs嵌套,stu[2] = 0, 也就是恢复到了2的位置，然后stu[2] = 1,表示在第二层的时候选择，此时再次遇到dfs，这个dfs里面 u= 3，可以打印，退出之后stu[2] = 0, 退出了之前的嵌套，依次类推即可‘

莫浅子

2022/11/21

5490

js对象中什么是可枚举性(enumerable)？[通俗易懂]

json jetbrains object

可枚举性（enumerable）用来控制所描述的属性，是否将被包括在for…in循环之中。具体来说，如果一个属性的enumerable为false，下面三个操作不会取到该属性。 * for..in循环 * Object.keys方法 * JSON.stringify方法

全栈程序员站长

2022/11/17

1.7K0

C++枚举数组的排列状态

c++permutation 数组

在C++中可以使用next_permutation来枚举数组的不同排列状态。小例子： #include<bits/stdc++.h> using namespace std; int main() { int n=3; int perm[100]; for(int i=0;i<n;++i) { perm[i] =i; } for(int i=0;i<n;++i) cout<<perm[i]<<' ';

灯珑LoGin

2022/10/31

6450

Objective-C使用位运算设计可复选的枚举

其他

在软件开发中，枚举是我们会经常会用到的一种编程方式，通过枚举，可以使我们的代码更具可读性与统一性。通常情况下，我们会通过typedef来定义一种枚举的类型来使用。例如：

珲少

2018/08/16

5520

C语言 | 枚举概述

c 语言 c++

在C语言中，如果一个变量只有几种可能的值，则可以定义为枚举类型，所谓“枚举”就是指把可能的值一一列举出来，变量的值只限于列举出来的值的范围内。

小林C语言

2021/05/10

8490

在Android中使用枚举注解而不是枚举

android 编程算法

很多开发规范都是不建议在Android中使用枚举的，在Android系统中使用枚举的开销是使用常量的2倍。一般地，在一个文件中定义常量

阳仔

2019/07/31

1.4K0

C语言 | 枚举概述

c 语言编程算法打包

这道理放在C语言学习上也一并受用。在编程方面有着天赋异禀的人毕竟是少数，我们大多数人想要从C语言小白进阶到高手，需要经历的是日积月累的学习。

小林C语言

2021/05/28

6210

【C语言笔记】枚举

编程算法

这个知识点很重要，到处能用得到。其可以与typedef来进行类比进行理解（可查看【C语言笔记】define与typedef的区别？）。除此之外，其还可以与枚举enum进行类比。

正念君

2019/06/26

9520

在Java 8下更好地利用枚举

其他

在我们的云使用分析API中，返回了格式化过的分析数据（这里指生成分析图）。最近，我们添加了一个特性，允许用户选择时间段（最开始只可以按天选择）。问题是，代码中每天中的时间段部分高度耦合了……

哲洛不闹

2018/09/14

8090

C语言（枚举类型）

c 语言编程算法

C语言中的枚举类型常年跑龙套当配角，不受待见，这当然是有其个人原因的。今天来个小知识，看看枚举为什么那么衰，也顺便看看怎么用。

用户2617681

2019/08/08

1.9K0

c语言枚举类型enum例子_枚举是什么意思

编程算法 https 网络安全

在实际的编程应用中，有的变量只有几种可能的取值，譬如说一个星期的七种可能，性别的两种可能等等。C语言为这种类型的变量的定义提供了enum关键字。

全栈程序员站长

2022/11/03

1.1K0

9.6 C语言枚举类型

c 语言编程算法打包

1、如果一个变量只有几种可能的值，则可以定义为枚举类型，所谓“枚举”就是指把可能的值一一列举出来，变量的值只限于列举出来的值的范围内。

小林C语言

2020/12/08

9560

C语言-枚举、共用体

单片机嵌入式 union 数据类型语法

前面章节学习了结构体，结构体里可以按顺序存放相同或者不同的数据类型，每个成员都有它对应的存储空间。而共用体和结构体一样也可以按顺序存放相同或者不同数据类型，但是与结构体的区别是，共用体所有成员共用一个存储空间，存储空间由成员中存储空间最大的来决定。

DS小龙哥

2022/01/07

8480

Go语言枚举和类型

package mainimport "fmt"//1.枚举的使用// 枚举指一系列相关的常量，比如下面关于一个星期中每天的定义。通过上一节的例子，我们// 看到可以用在 const 后跟一对圆括号的方式定义一组常量，这种定义法在Go语言中通常用于定义// 枚举值。Go语言并不支持众多其他语言明确支持的 enum 关键字。// 下面是一个常规的枚举表示法，其中定义了一系列整型常量：const( Sunday = iota //0 Monday //1 Tuesday //2

李海彬

2018/03/20

8010

ACM算法--枚举方法（指数枚举，组合枚举）模板

// 递归实现指数型枚举 vector<int> chosen; void calc(int x) { if (x == n + 1) { for (int i = 0; i < chosen.size(); i++) printf("%d ", chosen[i]); puts(""); return; } calc(x + 1); chosen.push_back(x); calc(x + 1); chosen.pop_back(); } // 递归实现组合型枚举 vec

风骨散人Chiam

2020/10/28

1.3K0

枚举

java

枚举就是尝试所有的可能性，尤其是当我们在确定一个问题是不是的这一类问题中尤其有用，例如说给一堆数，让我我们判断他们是不是素数，或者素数的数量的时候，这里他们就是判断类问题我们就可以使用枚举。但是注意这里我们需要考虑的就是枚举的方式，也就是枚举的角度。这里有一个小的例子就是最长回文子串的问题。首先我们就是用一个最简单的方式就是枚举出所有的字串，然后在这些字串里面找回文串。这样我们首先需要进行枚举就需要 n 平方的复杂度，然后我们还需要 n 的时间去判断这个串是不是回文，那么也

lwen

2018/04/17

1.2K0

[编程] C语言枚举类型（Enum）

打包

C语言枚举类型（Enum）: 定义形式为：enum typeName{ valueName1, valueName2, valueName3, ...... }; enum 类型名{名字1,名字2} 枚举变量,枚举值默认从 0 开始，往后逐个加 1（递增）

唯一Chat

2019/09/10

1.2K0

1-3递归实现组合型枚举

递归

从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。输入格式两个整数 n,m ,在同一行用空格隔开。输出格式按照从小到大的顺序输出所有方案，每行 1 个。首先，同一行内的数升序排列，相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。数据范围 n>0 , 0≤m≤n , n+(n−m)≤25 输入样例： 5 3 输出样例： 1 2 3 1 2 4

编程张无忌

2021/03/11

4560

相似问题

递归可枚举语言的闭包性质

可枚举包含可枚举

递归语言和递归可枚举语言的区别是什么？

图灵机中递归的还是递归的可枚举语言？

在可枚举项的可枚举项上调用.Distinct()

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

问递归可枚举(可计算可枚举)语言在排列下关闭？
EN