computation-theory

1열

1답변

Milner의 Pi 미적분학에서 여러 프로세스가 같은 채널에서 읽었을 때 평가의 의미는 무엇입니까?

Milner의 Pi 미적분학 (Milter 's Pi Calculus)에서 여러 프로세스가 같은 채널에서 읽었을 때 평가의 의미는 무엇입니까? 규칙은 말을 그 !x(a). P | ?x(b) Q ~> P | Q[a/b] 하지만 대한 !x(a). P | ?x(b) Q | ?x(c) R 같은 상황?

2열

3답변

다항식 시간 알고리즘을 사용하여 숫자 지수가 숫자인지 여부를 테스트 할 수 있습니까?

유명한 종이 PRIMES is in P을 연구하면 혼란스러워집니다. 알고리즘의 첫 단계는 If (n=a^b for nature number a and b>1), output COMPOSITE.입니다. 전체 알고리즘이 다항식 시간으로 실행되므로이 단계도 O (log n)^c에서 완료되어야합니다 (주어진 입력 크기는 O (log n)입니다. 일부 인터넷 검

2열

1답변

2 플레이어 게임은 다항식 공간입니다.

n x n 개의 게임 보드가 있으며 보드의 각 위치에는 정수가 있습니다. 플레이어 1은 행 1에서 번호를 선택하고 플레이어 2는 행 2에서 번호를 선택하고 더 이상 행이 없을 때까지 대체합니다. 그런 다음 합계가 미리 결정된 합계 S와 같으면 플레이어가 모든 수를 더하고 플레이어 1이 이깁니다. 그렇지 않은 경우 플레이어 2가 승리합니다. 특정 보드 및 합

-1열

1답변

컨텍스트 프리 언어의 통합

컨텍스트 프리 언어 모음은 항상 컨텍스트 프리입니까? 대답을 정당화하십시오 ..... 나는 대답이 '예'라는 것을 알고 있지만 어떻게 증명할 수 있습니까?

1열

1답변

일반 언어 및 증명 (계산 모델)

계산 과정의 모델에 대한 몇 가지 HW 관련 질문에 대한 도움이 필요합니다. 나는 텍스트 (Michael Sipser의 Computation Theory 소개)에서 관련 장을 읽었지 만,이 HW 문제는 책이 나에게주지 않은 지식을 필요로한다고 느낀다 ... 첫 번째 질문은 다음과 같다. 첫 번째 질문은 다음과 같다.) L * = {a} * {b} * 와 같

-6열

2답변

튜링 기계 시뮬레이터

나는 이런 식 입력 파일에 걸리는 C에서 튜링 기계 시뮬레이터 ++ 디자인해야 Z : q1,0, Q2, X, R T : 0,1, T를 X Q1,1, Q2, X, R T : q2,0, q2,0, R .. S : q1 F : q3, q4 Q는 상태, A는 입력 값, Z는 테이프 알파벳, S는 시작 상태, F는 수락 및 거부 상태입니다. 입력 수, 입력 문자열

2열

1답변

어떻게 실시간 상황을 시뮬레이트하는 알고리즘을 만들 수 있습니까?

저는 알고리즘을 잘 알고 있지만 실시간 문제를 변환하고이를 알고리즘으로 만들기 위해 완전히 배우지는 않습니다. 상황을 신비화하고 알고리즘으로 공식화하는 책/종이가 있는지 알고 싶습니다. (상황을 깨고 알고리즘을 선명하게하기위한 정신 능력을 훈련하는 것과 같습니다.) 이러한 몇 가지 문제에 접근하는 방법 중 일부를 보여줍니다. 모든 쉬운 학습 링크/자료가 도

1열

2답변

우리는 어떻게 문맥 자유 언어로 프로그램을 작성합니까? 튜링이 완료 되려면 재귀 적으로 열거 가능한 언어로 프로그램을 작성하면 안됩니까?

컨텍스트없는 언어로 작성하는 경우 튜링 기계 (재귀 적으로 열거 가능한 언어를 허용)의 출력을 어떻게 시뮬레이션 할 수 있는지 이해할 수 없습니다.

14열

2답변

Turing-Decidable과 Co-Turing-Decidable의 차이

저는이 두 가지의 차이를 이해하는 데 정말로 애 쓰고 있습니다. 내 교과서에서, 그것은 본질적으로는 튜링 - 인식 언어의 보완 인 경우 언어가 공동 튜링 인식 할 을 말함으로써 그 차이를 설명합니다. 나는이 정의의 일부분을 이해할 수 없다 : 튜링 인식 언어의 보완어 란 무엇을 의미합니까? 다른 언어의 보완어인지 정확히 어떻게 결정합니까?

1열

2답변

왜 많은 것들이 '인간의 관측 가능 시간'에 움직입니까?

저는 복잡한 이론을 연구 해 왔으며 견고한 프로그래밍 배경에서 왔으며 인간에게 내재 된 시대에 많은 것들이 실행되는 것처럼 항상 이상하게 보입니다. 왜이 사람이 어떤 아이디어를 가지고 있는지 궁금합니다. 나는 일반적으로 1 초에서 1 시간 범위의 시간을 말하고 있습니다. 시간의 범위가 얼마나 좁은 지 컴퓨터가 처리 할 수있는 초당 수십억 개의 연산에 비례한