Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [computer-science]

All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For questions from scientific computing, use (computational-mathematics).

Computer science is the study of the theory, experimentation, and engineering that form the basics for the design and use of computers. It is the scientific and practical approach to computation and its applications and the systematic study of the feasibility, structure, expression, and mechanization of the methodical procedures (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information. An alternate, more succinct definition of computer science is the study of automating algorithmic processes that scale.

Some fields of computer science such as computational complexity theory (which explores the fundamental properties of computational and intractable problems) are highly abstract, while fields such as computer graphics emphasize real-world visual applications.

5523 questions
2
votes
2 answers

Non-Deterministic Turing Machine Transition Function

Say a Non-Deterministic Turing Machine is in a state $q_1$ and it reads symbol $a$ from its tape. Is it possible to have two different transitions: $$(q_1,a) \rightarrow (q_{accept}, , L)$$ and $$(q_1,a) \rightarrow (q_{reject}, , L)$$
George Tseres
  • 123
2
votes
2 answers

Time complexity of the travelling salesman problem?

The dynamic programming approach breaks the problem into $2^n n$ subproblems. Each subproblem takes $n$ time resulting in a time complexity of $\mathcal{O} (2^n n^2)$. How are there $2^n n$ subproblems? Why does each subproblem take $n$…
user26649
2
votes
3 answers

What's the difference between a set and a language?

I'm very familiar with languages such as $L$={$a^n$ where $n$ is a prime number}. I know this language is decidable. However, I ran across a similar problem that asked if the set $X$ = {$p$ where $p$ is a prime number} is decidable or not. It…
pauliwago
  • 635
2
votes
1 answer

why does $B=\{ \langle M_i: \exists j < i . L(M_j)=\sum^* \} \in R$?

I'd like your help with understanding how come the following language is decidable (in $R$). Let $M_0,M_1,M_2,...$ numbering of all Turing machines over $\sum$, why does $B=\{ \langle M_i: \exists j < i . L(M_j)=\sum^* \} \in R$? I understand that…
Jozef
  • 7,100
2
votes
1 answer

Why does A=$\{\langle M_1,M_2,M_3 \rangle : L(M_1) \cap L(M_2) \ne L(M_3)\}$ isn't in $RE$.

I'm trying to figure out what's wrong with this following Turing machine which determinate that the following language A=$\{\langle M_1,M_2,M_3 \rangle : L(M_1) \cap L(M_2) \ne L(M_3)\}$ is in $RE$. I said that we can build a Turing machine that…
Joni
  • 189
2
votes
2 answers

NP-problem that needs superlinear certificates

In the definition of the complexity class NP, we allow the certificate to be polynomial in the input size. But do we ever need a certificate that is longer than the input? In all the NP problems I could think of, we don't. The "worst" problem was…
Sune Jakobsen
  • 995
2
votes
1 answer

How to find best combinations of numbers to make the sums as close as possible.

Say I am given eight numbers: 10, 8, 8, 7, 6. 5, 5, 4 I am told to divide the group of numbers in to two different groups, four numbers each. What formula or method is there for running every possible combination of numbers possible, and in the…
Jonah
  • 21
  • 2
2
votes
1 answer

Clarification about what is being asked in this computer science proof?

I am supposed to prove this statement(part of a presentation on MinML-Syntax and Static Semantics) using typing rules: If G, x:t |-- e’ : t’ and G |-- e: t then G |-- e’[e/x] : t’ I am lost about what this means. Is this using the standard…
Caffeinated
  • 521
2
votes
1 answer

Right-moving Turing Machines

The idea of a read-only right-moving Turing Machine already exists [1]. Is there a relaxed version of this where an input-reading head only moves right to read inputs as needed? There may be other heads doing the computation on work tapes; the…
ShyPerson
  • 1,720
2
votes
2 answers

Manually deducing the quadratic uniform B-spline basis functions

I'm trying to manually (i.e. without fancy equations like the Cox-DeBoor recurrence relation) deduce the quadratic uniform B-spline basis functions. In the book "Curves and Surfaces for Computer Graphics" it is explained, but there is one step that…
Ailurus
  • 1,192
2
votes
1 answer

The study of Mathematical Visualization , Where Do I start?

I've looked through the literature on this topic , but it seems way to complex for me. I need some help , would you guide me through the process , from beginning to end.
Jennifer
  • 21
  • 1
1
vote
1 answer

Evaluating math proofs by computer

Is there any way to evaluate (check) math proofs (entered in some convenient for computer form) by computer? Only thing that comes to my mind is functional programming, different logics, but I'm not sure if it has any relation.
baira
  • 107
1
vote
1 answer

Base conversion between base r^3 to r^2

The problem asks the following: If $(\alpha2)_{r^3} = (r3\beta)_{r^2},$ find $\alpha, \beta,$ and r. First off, I assume $r^2$ > 3 and $r^3 > 2$. I know that $(r3\beta)_{r^2}$ = (10 _ _ _ _ )$_{r}$ I've attempted to convert to base 10 and set…
Daniel Cazares
  • 715
1
vote
1 answer

When to use weak, strong, or structural induction?

For weak induction, we are wanting to show that a discrete parameter n holds for some property P such that P(n) implies P(n+1). For strong induction, we are wanting to show that a discrete parameter n holds for some property P such that (P(1) ^ P(2)…
user578053
1
vote
1 answer

Calculating MIPS

Been struggling to solve this question. From my notes, you can calculate MIPS through this formula: MIPS = Instruction Count / Execution Time X 10^6 And the question goes like this: Given an average instruction execution time of a computer(20…
Kidlat
  • 13
1 2 3
…
16 17