Questions tagged [function]
The function tag has no usage guidance.
18
questions
30
votes
1
answer
1k
views
Programming languages with canonical functions
Are there any (functional?) programming languages where all functions have a canonical form? That is, any two functions that return the same values for all set of input is represented in the same way, ...
- 403
17
votes
1
answer
4k
views
Universal Function approximation
It is known via the universal approximation theorem that a neural network with even a single hidden layer and an arbitrary activation function can approximate any continuous function.
What other ...
- 1,301
15
votes
1
answer
643
views
Why was Schönfinkel's work on eliminating "bound variables" in logic so crucial?
AFAIK, The first evidence of using higher order functions goes back to Schönfinkel's 1924 paper: "On the Building Blocks of Mathematical Logic" - where he allowed one to pass functions as ...
- 5,225
11
votes
1
answer
283
views
Existence of injective length-preserving rational function to a smaller alphabet
(This is a simpler rephrasing of an earlier question I have since deleted.)
Definitions
For this question, a finite-state transducer is like a standard NFA, except at each transition, the transducer ...
- 945
8
votes
0
answers
131
views
Can polynomial-sized circuits use garbage?
This is a non-uniform (and simplified) version of my previous question about Cook reductions. Let $R\subseteq \{0,1\}^*\times\{0,1\}$. A function $r\colon \{0,1\}^*\to\{0,1\}$ solves $R$ if $(x,r(x))\...
- 3,516
7
votes
1
answer
192
views
Composition of $FP$ and $\#P$ functions
Let $f_i \in FP$ and $g_i \in \#P$ for $i \in \mathbb{N}$.
It is known that: $f_1(f_2(x)) \in FP$ and that $g_1(f_1(x)) \in \#P$.
Is it known whether or not $f_1(g_1(x)) \in \#P$ or maybe $f_1(g_1(...
7
votes
0
answers
177
views
Universal approximation theorem of second order
The universal approximation theorem (https://en.wikipedia.org/wiki/Universal_approximation_theorem)
informally states that up to several conditions, any function can be approximated by a shallow ...
- 181
7
votes
0
answers
159
views
A class of functions on a lattice that are easy to optimize
Let $({\cal P}(X),\subseteq)$ be the subset lattice for a finite set $X$. Consider a function $f:{\cal P}(X)\to \mathbb{R}$ with the following property: Given any element $I_0\in {\cal P}(X)$, there ...
- 201
6
votes
1
answer
153
views
Combining (block)-sensitivity and Lipschitz conditions?
If we're given a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, we can define its sensitivity as follows. The sensitivity $s(f, w)$ with respect to input $w$ is the number of ways of flipping a ...
- 31.9k
3
votes
1
answer
302
views
Is there any good literature on the computational complexity of function problems?
There are some cstheory questions that touches function-problems. Like this:
Complexity class corresponding to sorting
So here is the question: Is there good literature about the computational ...
- 87
3
votes
2
answers
544
views
Constructing terms of function types out of the empty type
If a function $f$ is understood as its graph, i.e. a set of pairs $\langle x,y\rangle$ where $x$ is input and $y$ is output, then the empty set $\emptyset$ is a valid function, and for any set $A$, we ...
- 505
3
votes
1
answer
258
views
Cook reduction for search problems, by universal property?
A search problem is a relation $R\subseteq \Sigma^*\times\Sigma^*$. A function $f\colon \Sigma^*\to\Sigma^*$ solves $R$ if $(x,f(x))\in R$ for all $x\in\Sigma^*$. Define a search problem to be ...
- 3,516
3
votes
1
answer
260
views
Examples of nontrivial non-discriminatory functions
I am reading Cybenko's "Approximation by Superpositions of a Sigmoidal Function".
The paper defines a discriminatory function as:
$\sigma$ is discriminatory if for a measure $\mu$,
\begin{align}
\int ...
- 63
0
votes
1
answer
133
views
What is a known sequence for which being constant is not provable?
My question concerns the property of being constant for computable functions ${\mathbb N}\to \{0,1\}$, within any common framework $T$ strong enough to include Heyting arithmetic (and of course not ...
- 505
0
votes
1
answer
174
views
What is a "Covering Function"?
In Idris2, I will sometimes get an error telling me that a function "is not covering", which is apparently distinct from it not being total (and I do understand what a total function is). I ...
- 19
-1
votes
1
answer
226
views
Newbie question: Meta-functions?
Consider a function F that takes a function and produces a function based on structure of the input function. As an example consider F that takes all functions having at least two conditionals and ...
- 111
-1
votes
1
answer
75
views
Is function composition associative in non-pure programming languages?
We know that function composition is associative in theoretical programming languages such as STλC, and pure functional programming languages such as Haskell. Is the same true for languages where ...
-1
votes
1
answer
74
views
Multivariable concave function $(n - 1) f(x) >= \sum_{i=1}^{n} f(x_{-i})$
Define the multi-dimension concave function $f(x): \mathbb{R}^n_+ \rightarrow \mathbb{R}_+$ where $x \in \mathbb{R}^n_+$, here I use $\mathbb{R}_+$ to represent the range $[0, \infty)$ and we let $f(\...
user54970