Questions tagged [computability]
Computability theory a.k.a. recursion theory.
408
questions
4
votes
0
answers
88
views
Halting problem with minimal Turing Machine as promised input
Consider the following Turing Machine A.
Input: Turing Machine M that recognizes some language L(M)
Output:
If M is minimal (i.e. its length is minimum among Turing Machines that recognize the same ...
- 49
-1
votes
1
answer
93
views
Is any procedure satisified by the principle of least action able to be simulated by Turing Machine?
The Hamilton action $S$ is defined as following:
$$S=\int^T_0 L(q,\dot{q})dt$$
the integral along any actual or virtual (conceivable or trial) space-time trajectory q(t)
connects two specified space-...
- 1,077
-1
votes
1
answer
60
views
Computing non-halting inputs of semantic non-equivalent programs
Let P and Q be two programs take one natural number as input and produce no output and they are not semantically equivalent, that is, there exists at least one input value n such that either P(n) ...
-2
votes
0
answers
52
views
Source for the "Recursion Theorem" in the context of Turing Machines
Hi and thank you for reading me,
I saw a result that interests me in this lecture by Shalev Ben-David, called the "recursion theorem" (Theorem 19.1).
It roughly states that :
Fix an input ...
2
votes
0
answers
81
views
When is an upper bound on the longest irreducible program outputting something computable?
This is a repost of this mathoverflow question.
Given some way to to encode programs to strings with a finite alphabet, which we assume has a computable translation to/from Turing machines, a program ...
- 567
0
votes
0
answers
37
views
Integration of analytic function
It is the continuation of the question:
Complexity of analytic functions and integrals.
Given an input integer $t$ and a sequence of analytic functions $f_n(\cdots(f_0(x))$, with parameters $t$ itself,...
- 13
5
votes
2
answers
279
views
What are the computations model with a constant slowdown ? (and why do we care about Turing machines)
One problem with Turing machines is that the universal Turing machine $U$ can simulate any machine $M$ but with a $\log$ slowdown, meaning $U(\#M,x)$ runs in time $O(T(n)log(n) + O(n))$, where $n=|\#M|...
- 309
0
votes
1
answer
104
views
Deciding whether there are directed paths between two vertices of all possible lengths
I recently read a paper The presence of a zero in an integer linear recurrent sequence is NP-hard to decide by Blondel and Portier, in which they prove the statement
The problem of determining for a ...
- 109
8
votes
1
answer
169
views
Primitive recursive permutations
How to show that the inverse of a primitive recursive permutation of $\mathbb{N}$ is not necessarily a primitive recursive function?
- 115
5
votes
1
answer
195
views
Does every computable function have infinitely many "non-padded" representations?
It's well-known that every computable function has infinitely many representations (when they're expressed via recursive functions, or programs, etc.). I'm trying to understand whether there are ...
- 151
0
votes
0
answers
105
views
By Gödel numbering, is the set of computable(partially) transcendental numbers an immune set, productive set? [duplicate]
Every Turing Machine computing(output) real number is encoded as a natural number, namely, admissible numbering. Then what is the set of computable (partially) transcendental numbers? Is it an immune ...
- 1,077
-1
votes
1
answer
60
views
Computability/Complexity of optimization problems in general
Dear StackExchange community,
I have a question, or better phrased I am confused and would like to be enlightened by you!
So assume we have a (optimization) problem like that:
Instance: Let $f:\...
- 3
1
vote
0
answers
110
views
Why does the Time Hierarchy Theorem fail relative to promise problems?
Define Program Evaluation (PE) to be the promise problem of determining whether a program (written in a Turing-complete language) returns True or False. The promise is that the program will return ...
- 528
2
votes
0
answers
79
views
Many-one equivalence of sets that differ finitely
[This is a duplicate of my question from Mathematics Stack Exchange:
https://math.stackexchange.com/questions/4792354/many-one-equivalence-of-sets-that-differ-finitely
I am posting it here since it ...
- 115
3
votes
2
answers
546
views
Technical limitations of Turing machines due to the input and output encoding of values
Convention: Since I will be asking about some technicalities around Turing machines, it behooves to give a precise definition: say, here, “Turing machine” will stand for a $2$-symbol $1$-tape machine ...
- 851
0
votes
0
answers
132
views
Computational power of probabilistic automata
I am a bit confused about the proper role of probabilistic automata (PA) in the theory of computation.
Informally, I can imagine they can accept more than finite automata (FA) as they, for instance, ...
- 151
1
vote
1
answer
63
views
Many-one degrees of some particular sets
Let $W_0, W_1, W_2,\dotsc$ be an effective numbering of r.e. sets.
Consider sets $\text{Emp}=\{x\mid W_x=\emptyset\}$, $\text{Tot}=\{x\mid W_x=\mathbb{N}\}$ and $S_n=\{x\mid W_x=W_n\}$ (for some fixed ...
- 115
1
vote
0
answers
175
views
Decidability of the complexity of decision problems
This might be a question that is related to some of the existent questions on the topic in the title, but I still find some answers either not full, or the topic still slightly different (maybe due to ...
- 111
1
vote
1
answer
129
views
Primitive recursion with varying parameters
Suppose $g\colon \mathbb{N}^k \to \mathbb{N}$, $v_1,\ldots,v_r\colon \mathbb{N}^k \to \mathbb{N}^k$ and $h\colon \mathbb{N}^{k+r+1} \to \mathbb{N}$ are all primitive recursive, and define $f\colon \...
- 851
1
vote
1
answer
138
views
Complexity of analytic functions and integrals
There exist polynomial - time computable functions, log - space computable functions, and NC - functions. Given this:
To which class do analytic elementary functions, including trigonometric ones, ...
- 13
1
vote
0
answers
71
views
Primitive recursion relative to a logical system
In various places I have read that the normally considered non-primitive recursive Ackermann function is primitive recursive in higher-order logic. It's claimed to be due to "Reynolds, 1985",...
- 920
2
votes
0
answers
64
views
Complexity measures for semi-decidable problems
Is there any sensible complexity measure that makes sense to compare the "hardness" of undecidable semi-decidable problems? Time and space are of course not suitable, because they cannot be ...
- 1,704
0
votes
0
answers
72
views
What is the meaning of the additive epsilon term in the definition of a time constructible function?
There is a well-known theorem that states that a function $f$ is time constructible if and only if $f$ can be computed in time $O(f)$. But this theorem comes with some conditions: $f$ must be a ...
10
votes
1
answer
433
views
Is P=NP relative to the halting oracle?
Consider the following variant $\mathscr{H}$ of the halting oracle: given the code $e$ for an ordinary Turing machine and an input $n$ to it, we let $\mathscr{H}(\langle e,n\rangle) = \langle 0,0\...
- 851
7
votes
1
answer
301
views
Is there a well-defined notion of an “R/poly” complexity class?
This would be the complexity class of all problems that are decidable in finite time with a polynomial length advice string that can be arbitrarily hard to compute. But potentially undecidable without ...
- 353
3
votes
2
answers
158
views
What is formal definition of non-deterministic algorithm in context of primitive/general recursion?
I want to understand general method for formally defining non-deterministic algorithm. But all formal definitions I see are related to FSM/Turing-machines.
What is the reference for non-deterministic ...
- 315
1
vote
2
answers
131
views
Do realizable systems always have some non-well-founded sets?
Suppose we are standing outside a realizable system which admits CZF or a similar constructive set theory. Then consider the following:
LEM is not realized (e.g. this MSE answer)
The traditional ...
- 271
3
votes
0
answers
83
views
Generalizing Quines: Outputting an Arbitrary Function of Source Code
A Quine is a (non-empty) program $P$ that takes no inputs and returns its own source code $\langle P\rangle$ as the only output. For a function $f$ (with appropriate domains and range) define an $f$-...
- 119
4
votes
0
answers
325
views
How to prove that a language that allows infinite loops is still not Turing-complete?
CPS translations will always use pairs, either explictly or by currying. Though I can't find a reference for that, I'm assuming this is a necessary condition (I'd appreciate a reference if someone has ...
- 387
0
votes
0
answers
60
views
Input-Output Machines
From what I know, there is a vast literature on language recognizers in computer science.
Language recognizers are machines (e.g., Finite State Automata, Pushdown Automata, Turing Machines, ...) that, ...
- 101
4
votes
0
answers
137
views
Reference for "A Turing machine cannot be equipped with an oracle for itself"
Starting with a basic Turing machine, successive applications of the Turing jump produce successively more powerful machines, that can be indexed by any ordinal. A tempting error for students, and one ...
- 846
0
votes
0
answers
42
views
Computability for universal quantum turing machines
I would like to ask if anyone has any ideas about what a universal quantum turing machine (UQTM) can do as supposed to a classical universal turing machine (UTM) (i.e. quantum computer vs classical ...
8
votes
0
answers
134
views
Does Bellantoni-Cook safe recursion (or any other implicit characterization of P) admit Kleene's second recursion theorem?
Abstractly, by a programming language that operates on binary strings I mean a set $P$ of programs along with a semantics relation $[p](x) = y$, ``the program $p$ on string $x$ halts with output $y$.&...
- 851
1
vote
1
answer
113
views
Extension of primitive recursion, that is as powerful as System-T
I know that System-T restricted to first-order types is exactly as powerful as primitive recursive functions, because I proved it in Agda.
I asked myself, if there is a extension of primitive ...
-13
votes
3
answers
1k
views
What happens when the Linz halting problem proof is based on simulation of the input?
Applying a Simulating Halt Decider to the Linz Halting Problem Proof
Of course it is obvious that no halt decider H can possibly return a correct halt status for any input defined to do the opposite ...
- 43
0
votes
0
answers
63
views
Are there parsers that can parse languages in more expressive grammars than context-free grammars?
The Earley Parser is able to parse all context-free languages. Are there parsers that can parse say languages in context-sensitive grammars? I realize ambiguous grammars are non-deterministic and ...
- 101
2
votes
0
answers
128
views
Gurevich's theorem on primitive recursive functions being logspace-computable
I recently came across the following result attributed to Gurevich, according to which I understood that the class of problems solvable by primitive recursive functions is precisely the class L of ...
- 1,029
1
vote
0
answers
61
views
Generalization of computability to continuous for loops? [closed]
A computable function, formulated in the sense of mu recursion, can compute a for or do loop over some (possibly infinite) integer range.
I was wondering if a suitable generalization exists that ...
6
votes
1
answer
282
views
An analogue of Scott continuity for infinite-time-Turing-computable functions
$\newcommand{\tb}{2_{\!\bot}}\newcommand{\tbO}{\tb^{\,\omega}}$Let $2 = \{0,1\}$ and $\tb = \{0,\bot,1\}$.
Scott continuity is important for defining models of lambda calculus,
a formalism for ...
- 342
2
votes
0
answers
121
views
Are there more learnable but undecidable cases except the halting problem
Per request, I cross post the question here which is original from math.stackexchange
In the ICML 1996 paper, On the Learnability of the Uncomputables, by Richard Lathrop, he proved that halting ...
- 121
8
votes
1
answer
398
views
What are the application of Scott-Topology in theoretical computer science?
During a work I came across the Scott-Topology and I see that Scott-continuous functions show up in the study of models for lambda calculi. What I cannot understand is how this enrich the lambda-...
- 91
0
votes
1
answer
232
views
Understanding the construction of an uncomputable function
The following is from Arora and Barak's "Computational Complexity." I think one does not have to read the second paragraph of the proof to answer this question.
Theorem 1.10 There exists a ...
- 109
0
votes
0
answers
159
views
How can I switch into computability theory when I am part way through my PhD in deep learning?
I am partway through my PhD studying deep learning. I chose it just because it's useful and would yield a lot of industry opportunities. However, I am really missing my previous coursework in ...
- 101
3
votes
0
answers
86
views
Expressive power of lambda-calculus with restricted application
Consider a syntactic restriction of the (untyped) $\lambda$-calculus in which an application cannot have another application as an immediate subterm. More precisely, restricted terms ($R,S,...$) and ...
- 653
5
votes
1
answer
247
views
Why are some classes (ALL, ELEMENTARY, R, etc) badly behaved as oracles?
Some classes, such as ALL, ELEMENTARY, and R, are very badly behaved when used as oracles. For instance, all three of these classes trivially collapse P and EXP, even though (by the Time Hierarchy ...
- 528
3
votes
0
answers
124
views
Detailed proof of Theorem 2.1 in Papadimitrou book (Multitape TM to SingleTape TM)
I want to know if anybody knows a detailed proof of Theorem 2.1 of Papadimitrou's book Computational Complexity. The theorem states "Given any $k$-string Turing machine $M$ operating within time $...
- 51
7
votes
0
answers
139
views
Halting problem for finitary PCF
Is the halting problem decidable for finitary PCF? By "halting problem" I mean the problem of deciding whether a closed PCF term evaluates to bottom under the denotational semantics of PCF. ...
- 71
0
votes
1
answer
95
views
Is there a fundamental link between Nash's equilibrium and Turing's halting problem?
Since Nash equilibrium exists, is there a computational analogue of this equilibrium point? I am trying to approach Nash equilibrium from computational point of view to see if the equilibrium point ...
- 109
0
votes
1
answer
145
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
8
votes
1
answer
366
views
What is the complexity class of higher-order primitive recursion?
Short and sweet: The complexity class of primitive recursive functions (WP) is PR (WP, Zoo). What's the complexity class of higher-order primitive recursion (WP)?
The motivating context is simply that ...
- 271