2
$\begingroup$

Consider the set of all valid Turing Machines descriptions $T_{All}$, and the set of functions that denote the real (not asymptotic) running time of Turing Machines in $T_{All}$, lets call it $R_{All}$.

Since there are infinite functions, not all of which might represent the running time of a valid Turing Machine, how do we describe this subset of $R_{All}$ mathematically (say to a non CS individual) who doesn't know anything about TM etc.

Is there an accurate, self contained, complete mathematical definition that describe this subset of mathematical functions without referring to anything else like TM?

$\endgroup$
2
  • $\begingroup$ How about $R_{All} = \{x\in Z \mid x\ge 0\}$? $\endgroup$ Dec 22, 2022 at 18:38
  • $\begingroup$ @RickDecker: or $R_{All}=\mathbf N$, provided one can show that all naturals can be produced. $\endgroup$
    – user16034
    Dec 23, 2022 at 15:32

2 Answers 2

2
$\begingroup$

It is not possible to describe the subset of functions that represent the running time of valid Turing machines in terms of pure mathematics, without reference to the concept of a Turing machine. This is because the concept of a Turing machine is fundamental to the definition of this subset of functions.

A Turing machine is a mathematical model of a hypothetical computer that can perform any computation that is theoretically possible, given enough time and memory. The running time of a Turing machine is the number of steps it takes to complete a computation, as a function of the size of the input.

To define the subset of functions that represent the running time of valid Turing machines, we must first define the concept of a Turing machine and specify the conditions under which a function can be considered to represent the running time of a Turing machine.

For example, we could say that a function f(n) belongs to the subset of functions that represent the running time of valid Turing machines if and only if there exists a Turing machine M and an input x such that the number of steps M takes to compute f(|x|) on input x is equal to f(|x|). Here, |x| represents the size of the input x.

This definition captures the idea that the running time of a Turing machine is a function of the size of the input, and it links the concept of a Turing machine to the mathematical concept of a function. However, it does not provide a self-contained, complete mathematical definition of the subset of functions that represent the running time of valid Turing machines, as it relies on the concept of a Turing machine, which is not a purely mathematical concept.

$\endgroup$
1
$\begingroup$

Short answer: No.

These are called the time constructible functions. The definition is basically what you would expect it to be: a function $f(n)$ is fully time constructive if there is a Turing machine that, on input $1^n$, stops after exactly $f(n)$ steps. I'm not aware of any simple and complete characterization of the set of such functions that does not refer to Turing machines.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.