Questions tagged [function]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
11 votes
1 answer

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

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

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

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

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(\...
user avatar
3 votes
1 answer

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
7 votes
0 answers

Universal approximation theorem of second order

The universal approximation theorem ( informally states that up to several conditions, any function can be approximated by a shallow ...
  • 181
7 votes
0 answers

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

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(...
3 votes
1 answer

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 ...
15 votes
1 answer

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,175
3 votes
2 answers

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

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 ...
8 votes
0 answers

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

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 ...
30 votes
1 answer

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

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 ...
17 votes
1 answer

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