computability

1열

2답변

나는 Subset-Sum problem의 변형을 가지고 있는데, 부분 집합의 크기는 k이고 모든 정수는 양수 (0이 아님)입니다. 온라인에서 볼 수 있듯이이 질문은 의사 다항식 시간의 동적 프로그래밍을 사용하여 상당히 해결할 수 있습니다. 나는이 문제가 NPC이거나 P (P!=NP이라고 가정)이라고 결정해야합니다. 나는 부분 집합 합계 문제를 줄이려고했지만

1열

1답변

셀 수있는 모든 언어에 TM이 있습니까?

튜링 머신이 언어에 대해 존재한다면, 언어는 재귀 적으로 열거 될 수 있다는 것을 알고 있습니다. 따라서 언어에 대한 열거 절차가 있습니다. 그러나 언어가 중요하다면 TM이 있어야 함을 의미합니까? 감사합니다.

0열

1답변

튜링 기계가 정식 계산 모델이 튜링 완료인지 결정할 수 있습니까?

즉, 튜링 기계가 공식 시스템 S를 입력으로 사용하여 S가 튜링 완료인지를 결정할 수 있습니까? 이것이 결정 불가능한 문제라고 생각합니다. 맞습니까? 결정 불가능한 경우 왜 우리는 (인간으로서) 튜링의 완전성을 결정할 수 있습니까?

0열

1답변

언어에서 문맥 자유 문법으로 이동

주어진 언어 K = {e^h f^i | 2h> i> h} 문맥 자유 문법을 생성해야합니다. 내가 만든 몇 가지 제작 규칙은 다음과 같습니다. S -> eeTfff 및 T -> eTff | ε n = m + 1 인 경우에만 작동하지만 2h> i> h의 모든 조합에 대해 규칙을 생성하는 방법을 알지 못합니다.

1열

1답변

순열로 닫히는 반복적으로 열거 가능한 (계산 가능하게 열거 가능한) 언어?

L이 모든 언어 인 경우. L 재귀 적으로 열거 (computably 열거), 다음 파마 (L)되고 또한 재귀 적으로 열거하면 : 언어 파마 (L)는 L. 참 또는 거짓에서 단어의 모든 순열의 언어입니다. 이 질문은 L이 결정할 수있는 경우 perms (L)과 같은 최종 결론에 도달했습니다. 나는 거짓이라고 말할 것이라고 생각하지만이 주장을 뒷받침 할 증거

0열

2답변

Computability and Complexity에 대한 좋은 설명은 어디에서 찾을 수 있습니까?

나는 Computability and Complexity에서 반복적 인 일을 반복하고 있으며, 누구에게도 이런 종류의 연구를위한 훌륭한 자원이 있는지 궁금해하고있었습니다. 일반 언어, 문맥 자유 및 문맥에 민감한 언어와 같은 모든 것들이 있습니다. 예를 들어 : 당신이 볼 수 있듯이, 그것은 끔찍하게 표현한 질문이다. 강사가 우리에게 준 메모는 똑같이 나

0열

1답변

모든 비 재귀 언어가 무한하다는 것을 증명하십시오.

[title] 위의이 문장이 참인지 궁금합니다. 여기에 이미 나와있는 내용이 있습니다. 비 재귀 적 의미는 결정할 수 없습니다. 내가 읽은이 말한다 Are all infinite languages undecidable? : 언어가 결정 불가능하다 경우 (비 재귀), 일부 문자열은 TM은 IT가 INFINITE 반드시 가질 halt.SO에 실패 할이 있어야합

16열

4답변

정렬 알고리즘이 안정적인지 감지하는 블랙 박스 방법이 있습니까?

코드가 실행되는 대상 구현이 무엇인지 알지 못하는 JavaScript (일부 적용 가능)에서는 기본 정렬 알고리즘 (Array.sort)이 안정적인지 여부를 감지하는 기능이 있습니다. 다음은 the specification입니다. 나는 웹킷 (1)(2) 2 개 테스트를 찾을 수 있지만, 이러한 테스트는 어떻게 믿을 수 있습니까? (이 검사는 PCP으로 끝날

1열

4답변

Σ * 및 Σ을 공식 언어로 이해하기

이 있다면 Σ*에 어떤 단어가 있습니까? Σ*= {a,aa,aaa,aaaa.....}? 감사

1열

1답변

계산 가능성 : 제한된 수의 절이있는 SAT 수식

정의 SAT2016 = {\ phi | \ phi는 최대 2016 개의 절이있는 CNF 공식}입니다. P \ neq NP라고 가정하면 SAT2016 NP가 완성 되었습니까? 각 절의 리터럴 수는 한정되어 있지 않으므로 절 수에 상수가있는 수식의 적합성을 검사하는 다항 시간 알고리즘이 있는지 여부가 즉시 명확하지 않습니다. 귀하의 아이디어를 환영합니다.