We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [computability]

Computability theory a.k.a. recursion theory.

Filter by
Sorted by
Tagged with
0
votes
1answer
99 views

Enumerator for the language w#w^R? [closed]

I'm trying to build a Turing machine diagram for the language w#w^R, where w^R is the reverse of w, and w is a word made up of 0's and 1's. I'm trying to think of an algorithm but I can't think of ...
0
votes
1answer
183 views

In regards to the tautologies of a polynomially-bounded propositional proof system

In the book 'Logical Foundations of Proof Complexity', co-authored by Stephen Cook, the following definition is given: A proof-system $F$ is said to be polynomially-bounded if there is a polynomial p(...
0
votes
2answers
518 views

largest language class for which inclusion is decidable

am wondering what is the largest language class that is known for which set inclusion is decidable, ie a class such that if $A, B$ are in that class then $A \subset B$ is decidable. am also ...
0
votes
1answer
210 views

Halting on a (possibly one-way) write-once tape

Consider Turing machines (with the Busy Beaver "design specifications") that must write a 1 whenever they read a 1 (i.e., "write once"). ${}$1. $\:$ Is the halting problem decidable for these ...
0
votes
1answer
234 views

Simulation of deterministic turing machines

What are the best known upper and lower bounds for simulating t steps of certain models of deterministic turing machines (1 tape, 1 tape with read only input tape, 2 tape, multi tape, with/without ...
0
votes
0answers
59 views

Turing meta-oracle

Let H(P) be some program that given P('s source code) computes whether or not P terminates, i.e. solves the halting problem. H only needs to terminate if P terminates. (This disallows solutions like ...
0
votes
0answers
129 views

Oracle that will provide any computable information about another oracle

Suppose I have an oracle X. Then let Y be an oracle which will answer any computable question about X. In other words, Y takes as input a Turing program which can in turn make calls to X. Y then ...
0
votes
0answers
238 views

algorithm that can determine for every regular language L [closed]

can you please tell me how can I show that there exists an algorithm that can determine for every regular language L, whether or not |L| ≥ 5
0
votes
0answers
860 views

Understanding the HRU Model (Protection in Operating Systems)

As of now I am feeling terrible because I have spent the past 10 hours trying to understand this paper titled "Protection in Operating Systems" by Harrison, Ruzzo and Ullman. At this point, any help ...
-1
votes
1answer
625 views

Is there any way to differentiate between “sort of” Turing-Complete and “really” Turing-Complete?

Some things, like the computer language C, turing machines, lambda calculus, etc. seem to be "naturally" Turing-Complete. That is, they're just Turing-Complete from the bottom up. On the other hand, ...
-1
votes
1answer
107 views

Consistency and completeness of any arbitrary 3-valued logic? [closed]

Based on the explanations here [1] I know that 3-valued first order logic has many different versions, which differ in the definition of their operations (e.g. implication). All of these (as far as I ...
-1
votes
1answer
75 views

Is there an inherently ambiguous language which can not be recognized by Deterministic LBA?

Is there inherently ambiguous language which can not be recognized by Deterministic LBA? For example, $L=\{wv: w,v=(x|y)^*, w=w^R,v=v^R\}$, is there any deterministc LBA that recognizes $L$ ?
-1
votes
1answer
236 views

How can you prove that all halting probabilites are normal real numbers?

Wikipedia claims that any halting probability (Chaitin's constant) is a normal number. Since Chaitin's constant is uncomputble, how is a proof the the normalcy of the number possible? Computable ...
-1
votes
1answer
2k views

Decidability of the halting problem on finite computers [closed]

I've seen two competing and contrary arguments for this problem. One states that real computers are linear-bounded automata, and therefore the halting problem is decidable. The other states that ...
-1
votes
2answers
405 views

Complexity of problems solvable by primitive recursion

I was wondering if there is any known complexity of problem for which primitive recursive functions cannot solve. One such problem might be "is N the ackermann function for $k_1$ $k_2$" as it seems ...
-1
votes
1answer
127 views

Why does the Placid Platypus function grow faster than any computable function?

I came across the Placid Platypus function $PP(n)$ today, defined as the minimal number of states needed for a turing machine that prints a string of $n$ ones and halts. This function is claimed to (...
-1
votes
2answers
489 views

Are these problems in NP class?

${\bf New\ version}$ [Version 1.2] Let $f: \mathbb{N} \to \{0,1\}$ be a computable function, ${\bf Fin}(\mathbb{Z})$ be the set of all finite subsets of $\mathbb{Z}$, and $W: {\bf Fin}(\mathbb{Z}) \...
-1
votes
1answer
88 views

What is the relation between P-immune languages and NP-complete languages? [closed]

Can a NP-complete language be P-immune? Why can't existence of P-immune languages separate NP from P?
-1
votes
1answer
120 views

Gödel-Numbering of the Context-Sensitive Languages

I would like to have a Gödel-numbering of the context-sensitive languages. Because there is no obvious syntactic distinction between LBAs and TMs, I cannot number the former in an immediate way. So I ...
-1
votes
0answers
31 views

Understanding Computability of a Function

I know that computability is the proof of existence of an algorithm to solve a particular function in a infinite time but I can not understand how to decide that it is computable. How can we know ...
-2
votes
1answer
733 views

Is there any proof that a network made of Turing machines can't solve the halting problem? [closed]

My question points to the fact that Turing machines are isolated by definition. But what if they can send and receive information from/to other Turing machines? What if they can be "interrupted" at ...
-2
votes
1answer
597 views

Intersection between context-free and context-sensitive language decidability [closed]

I'm trying to find a formal proof of the following fact: Given a context-free language, say $L_1$, and a context-sensitive language, say $L_2$, it is NOT decidable if their intersection is empty ($...
-2
votes
1answer
119 views

Are there any known problems that require potential nontermination to solve? [closed]

Apart from problems that specifically have to do with Turing machines, like "Simulate a Turing Machine with the given description", are there any problems that require Turing-complete potentially ...
-2
votes
1answer
150 views

Undecidable Single Programs [closed]

So the halting problem basically states that there cannot exist any finite length algorithm for automatically verifying if other finite length algorithms terminate. But suppose I start listing out ...
-2
votes
2answers
545 views

how do you turn an algorithm for a decision problem into an algorithm for an optimization problem?

It is well-known, I believe, that theoretically, in quite a few cases, an algorithm that solves a decision problem can be turned into an algorithm that solves the corresponding optimization problem. ...
-3
votes
1answer
454 views

Help proving a 3CNF related prob. is in P

I need help proving that this problem is decidable in polynomial-time: Input: a 3CNF formula with more than one clause. Question: can the formula be divided into two satisfiable 3CNF formulas ? ...
-3
votes
1answer
704 views

Minimal Turing Machine implementation / Von Neumann UC [closed]

I've written a small python program which implements a Turing Machine with a finite tape. It has a tape, a head, a state register and a set of transfer functions ("the program"). The difference to a ...
-3
votes
1answer
450 views

What meaning (value) does Gödel's Incompleteness Theorems have for computation theory? [closed]

I've read Gödel's Proof by Nagel & Newman and I feel confused about there philosophical remarks on impossibility of computer to emulate human's mind. I don't understand how does that really ...
-3
votes
1answer
139 views

Could you explain to me the reduction? [closed]

I am looking at the following solved exercise: I haven't really understood at the reduction the part that we construct for each number $a_i$ a package of measurement $(\frac{4}{A}a_i, 5,3)$. Why do ...
-4
votes
1answer
134 views

What is the relationship between tail recursion with other recursions? [closed]

I'm rather confused by the recursion theory. From the link, the recursion theory was formed by Dedekind, Gödel and some other famous mathematicians. There are the following types of recursion. But ...
-4
votes
2answers
652 views

Is halting that hard? [Yes] [closed]

I want to make a modification to the halting problem. The output now has two possibilities: This program halts and it does not have the crossing structure (defined below); This program does not halt ...
-5
votes
1answer
1k views

Alternative Turing Machine Proofs

I am asking this question again. I am aware of, and have read the other similar "alternative proof TM" questions, but unfortunately, they do help me. I am looking for a TM Halting Problem proof that ...
-5
votes
1answer
124 views

Are there proofs which show that AIs are bound to be “worse” than the human brain? [closed]

I was talking with two PhDs (both teach IT related subjects) about artificial intelligence the other day. They were in agreement that an AI can never reach the level of the human brain, but failed to ...
-7
votes
2answers
579 views

Validity implies NP=#P? [closed]

Valid progams for NP imply every solution is a valid answer. NP not equals #P implies not all solutions are answers. Therefore, Validity implies NP=#P. NP is the problem class for ...
-10
votes
2answers
632 views

is every “nontrivial” algorithm Turing-complete?

recently there was a big response here to a question relating to the Church-Turing thesis.[1] this is another question that has nagged at me for close to a decade after studying some areas of TCS (...