Questions tagged [computability]
Computability theory a.k.a. recursion theory.
387
questions
1
vote
0
answers
51
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,558
0
votes
0
answers
57
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 ...
9
votes
1
answer
291
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\...
- 365
7
votes
1
answer
274
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 ...
- 261
3
votes
2
answers
116
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 ...
- 271
1
vote
2
answers
93
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 ...
- 273
3
votes
0
answers
71
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
303
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 ...
- 377
0
votes
0
answers
52
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
109
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 ...
- 807
0
votes
0
answers
36
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
107
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$.&...
- 723
1
vote
1
answer
82
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
2
answers
995
views
Can you see that the Linz Halting Problem proof contains a fatal flaw?
Applying a Simulating Halt Decider to the Linz Halting Problem Proof
When a simulating halt decider correctly simulates N steps of its input it derives the exact same N steps that a pure UTM would ...
- 63
0
votes
0
answers
61
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
1
vote
0
answers
95
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 ...
- 679
1
vote
0
answers
56
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
265
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 ...
- 332
2
votes
0
answers
108
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
7
votes
1
answer
275
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-...
- 81
0
votes
1
answer
202
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
129
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
78
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
235
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 ...
- 506
3
votes
0
answers
119
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
134
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
85
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
141
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
293
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 ...
- 273
2
votes
1
answer
238
views
A variant of two-counter machine
I would like to show that the halting problem for some variant of two counter machine (Minsky machine) is undecidable:
instead of "if c=0 goto i else goto j", there are "if c>d goto ...
5
votes
1
answer
833
views
Is coRE closed under concatenation?
I know that RE is closed under union, intersection, and concatenation (but not complement). It is likewise easy to show that coRE is closed under union and intersection (but not complement). What ...
- 10.2k
0
votes
0
answers
159
views
Is BigInteger-based Brainfuck Turing Complete?
All of the proofs of Turing-Completeness I've found for Brainfuck rely on its cells being fixed-width integers that wrap around upon over/underflow. The "parent language" P'' on which ...
- 119
2
votes
0
answers
109
views
Halting behavior of a randomly selected Turing machine?
Let $TM(k,2)$ be the set of Turing machines with $k$-states and $2$ symbols. Let $h(k)$ be the number of machines in $TM(k,2)$ that halt when run on the blank input.
Is
$\lim_{k \to \infty} \frac{h(k)...
- 251
3
votes
0
answers
60
views
Is relativization statement-dependent or proof-dependent?
I'm relearning some computability theory, and have encountered the idea of relativization of results to arbitrary subsets of $\omega$ and the subtlety of figuring out what the correct relativized ...
- 139
-2
votes
1
answer
133
views
Where, if any, is there currently any research being done on the subject of ternary computers? [closed]
I had the experience several years ago of working with a team that had developed a ternary computing system. It ran out of funding and was abandoned but I felt it was ahead of its time. Currently, ...
- 107
3
votes
1
answer
296
views
Proof and computational complexity
I couldn't find documents elaborating on this: if the Curry Howard correspondence is to be interpreted as establishing a strong relation between proofs and programs, should there not be a strong ...
- 919
1
vote
0
answers
53
views
A proved computationally-irreductible function
In arXiv:1111.4121 and arXiv:1304.5247, Hervé Zwirn and Jean-Paul Delahaye propose a formal definition of computational irreducibility. Is there a (possibly artificial) function that can be proved to ...
- 381
0
votes
0
answers
505
views
What is the difference between a model of computation and a programming language?
https://en.wikipedia.org/wiki/Model_of_computation includes sequential models, functional models and concurrency models.
Sequential models include finite state machine, Turing machines, random access ...
- 639
4
votes
1
answer
279
views
Is this variant of bitwise cyclic tag Turing-complete?
Cross-posted to MathOverflow.
CT is an extremely minimalist programming language that can simulate arbitrary tag systems, and is therefore Turing-complete. A program consists simply of a string of 3 ...
- 651
3
votes
1
answer
150
views
What is the meaning of 'uniform' in Blum's paper "On the Size of Machines"
In Blum's "On the Size of Machines" he uses the word 'uniform' in several places.
For instance, in Theorem 1, he writes
Let $f$ be any recursive function. Then there exists $i,j\in \mathbb{...
- 41
15
votes
1
answer
693
views
Computability and continuity
Say $L_1$ and $L_2$ are computable languages. Let $f$ be a function $L_1 \rightarrow L_2$. Let $C$ be the statement, "if $l \subseteq L_2$ and $l$ is a computable language, the preimage $f^{-1}(...
- 255
-1
votes
1
answer
124
views
Are all computable functions monoidal from a category theory POV? [closed]
I have been studying some category theory only to understand the "why" behind the various categorical constructs we use ("borrow") in the world of functional programming.
One of ...
- 5,255
16
votes
1
answer
350
views
Is there a language of first-order logic such that every r.e. set is Turing-equivalent to some finitely axiomatizable theory in that language?
I hope that mathematical logic / recursion theory type questions are welcome here. I am sorry this question is so long and technical, but I believe that if you read it you will find that it is well-...
- 303
1
vote
1
answer
268
views
How come Wikipedia says that Random Turing Machines can provide uncomputable output?
Wikipedia article mentioned : Hypercomputation
The third paragraph starts off with:
Technically, the output of a random Turing machine is uncomputable; however, most hypercomputing literature focuses ...
- 173
1
vote
1
answer
169
views
What kind of computational model is the brain? [duplicate]
I was wondering what kind of computational model is the human brain (as it seems superior to a Turing machine).
Another thing that should be a separate question, What would be a perfect computer model ...
- 133
12
votes
2
answers
578
views
Complexity relative to the graph of the Busy-Beaver function
This question is inspired by the comments made on this other question that I asked, and by an attempt to provide an explicit example of a complexity question beyond the Turing degree $\mathbf{0}$. (...
- 365
5
votes
0
answers
251
views
Has there been any development of complexity theory for other Turing degrees than 0?
(I'm not sure if this question is better suited for MathOverflow or here. I'll try here first, and move over to MO later if it appears to be more appropriate.)
Complexity theory can be very broadly ...
- 365
1
vote
0
answers
94
views
Given a program specification, S, what can be said about the size and efficiency of programs that exactly satsify S, with respect to the size of S?
Suppose we are given a program specification, $S$, and we want to reason about programs $P$ that satisfy $S$. One might like to think that if the specification is 'simple', the the program should be '...
- 41
4
votes
0
answers
105
views
Logic of learning
Does Robust logic (Leslie Valiant), Default logic (Raymond Reiter) and Circumscription logic (John McCarthy) have any relation?
I was Mathematician and Computer Science (dual degree undergraduate) ...
-2
votes
1
answer
116
views
Definition of Omega Jump [closed]
In the book Computability theory (Rebecca Weber) I stumbled about Exercise 7.1.24 with the definition of the omega jump.
The book says:
The omega jump of $A$, $A^{(\omega)}$ is the join of all $A^{(n)}...
- 1