Explore BrainMass

Theoretical Computer Science

Theoretical computer science is a division of general computer science and mathematics which focuses on the abstract and mathematical aspects of computing. The field of theoretical computer science is interpreted broadly to include algorithms, data structures, computational complexity, distributed computing, parallel computing, and quantum computing. Work in this field is often distinguished by its emphasis on mathematical technique and formal proofs.

Formal algorithms have existed for many years. However, it was not until 1936 when Alan Turing, Alonzo Church and Stephan Kleene formalized the definition of an algorithm. These developments have led to the modern study of logic, computability and computer science as a whole. Now the filed is abuzz with talk of the future of quantum computing, the most exciting potential future path that modern computing might take.

Turing, Church (credit: Princeton University, Institution of Mathematics) and Kleene (credit: Konrad Jacobs, Erlangen)

The most important fields of theoretical computer science, and accordingly, those most often taught and studied, are as follows:

  • theory of computation, including automata, computability and computational complexity theories
  • programming language theory
  • compiler theory
  • artificial intelligence

Categories within Theoretical Computer Science

Programming Language Theory

Postings: 29

Programming language theory deals with the design and implementation of different computer science languages.

Compiler Theory

Postings: 17

Compiler theory deals with the design, implementation and optimization properties of language compilers.

Amdahl's Law

(a) Illustrate Amdahl's law in terms of speedup vs. sequential portion of program by showing the speedup for N = 8 processors when the sequential portion of the program grows from 1% to 25%. (b) ( Amdahl's law) With sequential execution occurring 15% of the time: (i) What is the maximum speedup with an infinite number of

Theory of computation

Summarize the significance of the halting problem in the field of theoretical computer science.

Write a Turing machine algorithm to perform a unary decrement.

Write a Turing machine algorithm to perform a unary decrement. Assume that the input number may be 0, in which case a single 0 should be output on the tape to signify that the operation results in a negative number. When writing Turing machine algorithm, include comments for each instruction or related group of instructions.

Logic: Turing Machines

Please see the attached file for the fully formatted problems. (a) We wish to design a Turing machine which, using monadic notation, inputs a pair (in, n) of positive integers in standard starting position (on an otherwise blank tape), and which halts scanning the rightmost of a string of in is on an otherwise blank tape. W

Turing-recognizable language

Let A be a turing-recognizable language consisting of descriptions of Turing machines, {M1, M2,...}, where every Mi is a decider. Prove that some decidable language D is not decided by any decider Mi whose description appears in A. (Hint: You may find it helpful to consider an enumerator for A.)

Turing Machine Probabilities

Let B be a probabilistic polynomial time Turing machine and let C be a language where, for some fixed 0 < &#61646;1 < &#61646;2 < 1, a. w &#61647; C implies Pr [B accepts w] &#61603; &#61646;1, and b. w &#61646; C implies Pr [B accepts w] &#61619; &#61646;2. Show that C &#61646; BPP. HINT: Use Lemma 10.5 to help you


Let &#61542; be a 3cnf-formula. An &#61625; assignment to the variables of &#61542; is one where each clause contains two literals with unequal truth values. In other words an &#61625; -assignment satisfies &#61542; without assigning three true literals in any clause. a. Show that the negation of any &#61625;-assignment to

Automata and Computability: Example Problem

Recall that NPSAT is the class of languages that are recognized by nondeterministic polynomial time Turing machines with an oracle for the satisfiability problem. Show that NPSAT = 2P. See attached file for full problem description.

Automata and Computability

Consider the problem of testing whether a Turing machine M on an input w ever attempts to move its head left when its head is on the left-most tape cell. Formulate this problem as a language and show that it is undecidable.

Automata and Computability

Show that the collection of Turing-recognizable languages is closed under the operations of a. union. b. concatenation. c. star. d. intersection

Automata and Computability

A Turing machine with doubly infinite tape is similar to an ordinary Turing machine except that its tape is infinite to the left as well as to the right. The tape is initially filled with blanks except for the portion that contains the input. Computation is defined as usual except that the head never encounters an end to the t

What major features should a perfect programming language include?

I have noticed that there are many languages, is this because no one language has all the major elements needed to be a perfect programming Language? What major features should a perfect programming language include? I am trying to understand the concepts and struggling.

Turing Machine for even palindromes

Construct a turing machine that accepts the language {ww^R : w <- {a,b}+}, where w^R denotes w superscripted R - reverse of w. For example, if w = abb then w^R = bba ww^R = abbbba

Turing machine with input in unary notation

Devise a Turing machine with input given in unary notation (i.e., a string of n 1's denotes the integer n, and numbers are delimited by 0's) such that the machine produces the following output: 0 if x is divisible by 4 1 if x is congruent to 1 modulo 4 2 if x is congruent to 2 modulo 4 3 if x is congruent to 3 modulo