1
vote
1answer
28 views

Are there differences between total functions, epimorphic functions and surjective functions?

I've read three definitions which seems to point to the same idea. I've read about epimorphic functions in Mazzola's Comprehensive Mathematics for Computer Scientists - in this book, he treats it as ...
1
vote
4answers
57 views

Examples of partial functions in which the domain is not known?

I was reading this, it mentions about a kind of function in which the exact domain is not known. The only example given is this one - and I'm not really sure I understood it. I got curious about it: ...
0
votes
1answer
50 views

Discrete Math: Functions and Set Questions

1) Consider the function: $f: \mathbb{R} \to \mathbb{R}$ (Real to Real Number), where $f(x)=2+x^2$, what would be all of the preimages of $3$? 1) $11$ 2) $11$, $-11$ 3) $1$, $-1$ 4) $1$ 2) Let $D ...
1
vote
1answer
54 views

Subscript before a function symbol?

Does anyone know what the subscript before the function means? $$ _pf_p $$ It's part of a definition for selfish routing in networks: Let $N = (V,E)$ be the network, which is a directed graph. ...
2
votes
1answer
47 views

Are all constrtuctively describable functions continuous? Do they necessarily come with a topology?

In the paper "An injection from $\mathbb{N}^\mathbb{N}$ to $\mathbb{N}$" by @AndrejBauer, about the question whether there exists an injection $\mathbb{N}^\mathbb{N}\to\mathbb{N}$, we writes ...
0
votes
1answer
50 views

How to prove such program is uncomputable

We say that two programs are equivalent if they give the same output on every input. Prove that it is impossible to write a computer program that takes as input two pieces of code, code1 and code2, ...
0
votes
1answer
67 views

How can I tell/compare the asymptotic complexity of a function?

For something, like a quadratic I just take the highest degree and see if it is theta or big O or Omega of n, correct? So like 2n^2+2n+1 could be theta(n^2). What are the general ...
0
votes
1answer
311 views

Ceiling to Floor Function Conversion Proof

I am working on a proof to convert a ceiling of a fraction to a floor of a fraction. I found this: \begin{aligned} q=\left\lceil \frac{n}{m} \right\rceil \;&\Leftrightarrow\; \frac{n}{m} \leq q ...
1
vote
2answers
87 views

What's the term for a value x that satisfies the constraint $f(x) = f$ for a function f?

I know that $x$ is called the fixed point of a function $f$ if it satisfies the constraint $f(x) = x$. However, for a function $f$ if there exists some value $x$ such that $f(x) = f$ then what is the ...
2
votes
0answers
77 views

Upper bound for linear function

What may be more surprising is that when $a>0$, any linear function $an +b$ is $\mathcal{O}(n^2)$ which is easily verified by taking $c = a + |b|$ and $n_o = \max (\frac{-b}{a}, 1)$. $$an + b ...
0
votes
0answers
34 views

Expressing functions using Karnaugh map [duplicate]

Using the Karnaugh map, express the following function: $F(0, 1, 4, 5, 8, 10, 11, 12, 13, 15)$ would this be the answer I'm a little confuse ($b_1=0$ and $b_0=0$) or ($b_3=0$ and $b_1=0$) or ...
-1
votes
1answer
150 views

How to show if a function is partial recursive?

I have seen and understood the most definitions but i just could not understand how to show if a function is mu-partial recursive or not. I used search engines, but all I find are just more lectures ...
2
votes
5answers
290 views

Converting an IF condition to a mathematical equation

I am trying to study about converting algorithms into mathematical equations. For this I just started with a simple random example : ...
-4
votes
2answers
385 views

How do I turn this piecewise function into a “normal” function?

I am a Java developer building a web app that I will be deploying "in the cloud" (I hate that expression) in a few months. I'm trying to develop a function that will let me spawn and kill the right ...
2
votes
1answer
48 views

Terminology for a function computed by a finite-state transducer?

A finite-state transducer is a generalization of a finite state machine that accepts an input string and produces an output string (instead of just accepting or rejecting). Is there a name for a ...
3
votes
2answers
200 views

Alternate expression for the following function

So if the following function is evaluated with the floating-point arithmetic, we get poor results for certain range of values of $x$. Therefore, I need to provide an alternate function that can be ...
2
votes
3answers
575 views

calculating unique value from given numbers

let's say I have some (n) random numbers 12, 13, and 18. I want to calculate some unique value from these three such that if I change their order 13, 12, 18 or 18, 12, 13..whatever order they are in, ...
0
votes
0answers
31 views

Some problem with function, operator, and optimization.

Actually, this problem come from a programming language challenge. The objective is: to create a one-to-one function, $f$, that mapped A into B with A = {0, 1, 2, 3, 4, 5, 6}, and B = {1, 5, 10, 50, ...
2
votes
1answer
254 views

Perfect Hash Function just an Injection?

I just read up on the concept of perfect hash functions on a set $S$. I am quoting: "A perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with ...
4
votes
3answers
701 views

non time constructible functions

A function $T: \mathbb N \rightarrow \mathbb N$ is time constructible if $T(n) \geq n$ and there is a $TM$ $M$ that computes the function $x \mapsto \llcorner T(\vert x\vert) \lrcorner$ in ...
2
votes
2answers
286 views

Step function for greaterthan

I need to avoid using an if statement that does a $\geq$ comparison, (I'm writing HLSL code for the xbox). I need a function such that $f(x, y) = 0$ when $x < y$ and $f(x,y)=1$ when $x \geq y$. ...
0
votes
2answers
395 views

How can I determine the cardinality of a set of polymorphic functions?

It seems obvious to me that the set of functions with the signature $\forall A. A \rightarrow A$ is "once-inhabited", i.e. there is only one such polymorphic function which "works" for any set $A$, ...