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
0
votes
1 answer

Functions in "Introduction to the Theory of Computation 3rd Edition by Sipser"

Consider this text from page 7 of the book in the title. "In the case of the function abs, if we are working with integers, the domain and the range are Z, so we write abs : Z−→Z. In the case of the addition function for integers, the domain is the…
0
votes
1 answer

complement arithmetic

in 10's complement arithmetic if i want to do (67-80) then 20 is 10's complemented.....and (67+20 = 87) no end carry i.e. result is in 10's complement form so the result(87) is 10's complemented(becomes 13) and a -ve sign is attached so the final…
0
votes
0 answers

How to calculate the characteristic Function with a Turning-Machine?

I have the following question that I need to answer : Proof that the set $P=\{w \in \{0,1\}^{*}|w \ is \ divisible \ by \ 2\}$ is decidable. Construct a Turing-Machine which calculates the characteristic Function of $P$. It is very obvious to me…
Iwan5050
  • 385
0
votes
0 answers

Derivation of the mathematical equivalent of NOT operation

I was browsing wikipedia (https://en.wikipedia.org/wiki/Bitwise_operation) when I came across this mathematical equivalent of the bitwise NOT operation. I can't find a derivation of this anywhere and wondered if anyone knows where it comes from?
0
votes
0 answers

Turing Decidability definition

A language is Turing-decidable if there exists a Turing machine that always accepts strings in the language, rejects strings that are not in the language, but never loops. Why is this statement false? "never loops" should be "neven infinitely…
0
votes
1 answer

Resize Images (maths for calculating values of new, unknown pixels).

So I am working on a project which resizes images in Matlab, however, I have decided to not use the in-built functions, but rather understand how this is done mathematically. So far I have a decent idea of how to scale the dimensions and re-allocate…
Sans_P
  • 1
0
votes
0 answers

Minimum Equal Pairs in Set Containing Specific Values

I'm currently working on a program which involves presenting equal pairs of values to a user, from a list pseudo-randomly populated with values between 1 and 8. E.g. [1,5,5,4,3,4,5,5] would return 3 pairs of equal values: (5,5) (4,4) (5,5) How would…
0
votes
1 answer

can you determine the distinct variable bit packets from within this bitstream?

11001101111011000011000111001011010011010111011011100011100111101011 the above bit stream should break up into these variable bit packets 11 0011 0111 1011 000011 000111 001011 010011 010111 011011 100011 100111 101011 basically it is a base 3…
0
votes
0 answers

2-universal hash-function

In my theoretical computer science course the professor left followed statement open (so we could create our own proof), but i really do not understand it: Let $s \in \mathbb{N} $ and $p \in Prime$. For every $a \in \{1,...,p-1\}$ let…
Luisa
  • 1
0
votes
0 answers

Few questions about Turing machines.

i started to college about computer sciences this year and i have few questions about Turing Machines. I will be very glad if you answer. Sorry for my bad English if i have mistake. Can Turing machines recognize irregular languages ? Are Turing…
0
votes
2 answers

How can I calculate the rating of multiple Nodes?

I have four nodes, that sends numbers between 1 and 10000 to the main-node. The value of every node should be between certain numbers: $$10 < node1 < 15$$ $$12 < node2 < 45$$ $$50 < node3 < 76$$ $$800 < node4 < 1200$$ Use case 1: Ideal set of nodes,…
gola
  • 17
0
votes
1 answer

Formula Manipulation?

I have a specific formula = $a$^2 + $b$^3 = $c$^2 and let's say I need to print out $a$ and $c$, but only $b$ is given to us. Example (I could think of): B = 3 3 ^ 2 + 3 ^ 3 => 9 + 27 = 36 (6 ^ 2) So we would just output 3 and 6 since it works based…
0
votes
1 answer

Is $\{(x, y) \mid y \in \text{Range}(\phi_x)\}$ decidable?

Is the following language decidable? A decidable language must be recursive, right? How should I show that the following is or is not recursive? $$\{(x, y) \mid y \in \text{Range}(\phi_x)\}$$
Gigili
  • 5,503
  • 8
  • 41
  • 62
0
votes
1 answer

How to convert from a flattened 3D index to a set of coordinates?

I have a flattened 3D array in row-major format with an index, $I$, defined as $I = x + y D_x + z D_x D_y$, where $x$, $y$, and $z$ are the indices and $D_x$, $D_y$, and $D_z$ are the dimensions of the 3D array. How can I obtain the original set of…
0
votes
1 answer

Recurrence relations by forward substitution help

My question is to solve the following using recurrence relation forward substitution then verify using mathematical substitution: $T(n) = 2T(\frac{n}{3})$ for $n > 1$, where $n$ is a power of $3$ $T(1) = 3$ I'm not sure where to start as I'm…
Dereck
  • 131