80 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
0
votes
1
answer
293
views
Prove that the following problem is undecidable by a reduction from the halting problem:
Prove that the following problem is undecidable by a reduction from the halting problem:
"Does a given Turing Machine M accept any string of form a^2k for k ≥ 1?"
I'm having trouble understanding the ...
1
vote
1
answer
156
views
Can we assure a strictly decreasing function is computable?
I've been assigned to solve an exercise that questions the following:
Suppose a function f: N->N that is strictly decreasing. Can we assure f is computable?
So far I've found that all non-...
1
vote
1
answer
726
views
Why do we define equivalent turing machines as two turing machines with the same accepted languages?
From many textbooks about computability, I see how we define equivalent turing machines as follows:
Two turing machines TM1 and TM2 are equivalent <=> L(TM1) = (TM2)
where L(TM1) is the ...
0
votes
1
answer
2k
views
Disjunctive Normal Form and satisfiable is in P (DNFSAT)
I am reading that a language that is in Disjunctive Normal Form and is satisfiable is a language in P, but there is no explanation, could anyone tell me why?
2
votes
1
answer
86
views
Make the assumption that P = NP [closed]
Suppose P = NP, would that mean that Hamiltonian-Cycle is no longer NP-Hard? Hamiltonian-Cycle is a language where a given graph G contains a Ham-Cycle.
user avatar
user7821248
1
vote
2
answers
218
views
Equality between two propositions nat -> nat
I am currently working in a project in coq where I need to work with lists of nat -> nat. So basically I will have a definition that takes a list (nat -> nat) and a proposition f : nat -> nat ...
1
vote
1
answer
199
views
Inputs to Program to Illustrate Halting Problem
Is this illustration of the haling problem correct?
function halts(func) {
// Insert code here that returns "true" if "func" halts and "false" otherwise.
}
function ...
1
vote
1
answer
910
views
"Reduction" from the complement of the universal language (L_u) to the language of nonempty-language Turing machines (L_ne)
I have a question from the domain of theoretical computer science.
The so-called universal language, L_u, is composed of pairs (M, w) such that w \in L(M). The language L_ne consists of machines M (...
1
vote
1
answer
380
views
How to define a function with Church numerals in lambda-terms?
How can I express the following function by a lambda term?
f(n) = T if n != 0.
F if n = 0.
n stands for a Church numeral.
I know that 0 := λf.λx.x where λx.x is the identity function and all other ...
1
vote
1
answer
268
views
How to define a coding function for all finite subsets of N?
For working with countable sets I have to define a coding function of all finite subsets of N (natural numbers). How can I do this?
I started with finding a function for all natural numbers: f(n)=1+2+....
1
vote
2
answers
87
views
Proving the inexpressibility of a function in a given language
I'm currently reading through John C. Mitchell's Foundations for Programming Languages. Exercise 2.2.3, in essence, asks the reader to show that the (natural-number) exponentiation function cannot be ...
0
votes
1
answer
1k
views
proving that a language is part of a grammar and vice versa
so here a grammar R and a Langauge L, I want to prove that from R comes out L.
R={S→abS|ε} , L={(ab)n|n≥0}
so I thought I would prove that L(G) ⊆ L and L(G) ⊇ L are right.
for L (G) ⊆ L: I show ...
0
votes
1
answer
464
views
How do you prove whether a simple unmeaningful code is computable or not?
The characteristics of a computable problem are:
Complete means that it covers all the cases;
Mechanistic means that it is precise;
Deterministic means that the same output will be provided if the ...
-2
votes
2
answers
102
views
What is the most concise way to generate strings of language anbncn using JavaScript without using loops?
To convey the merits of Lambda Calculus, and even JavaScript's ability to implement such (Turing-complete) formulas, I'd like to see the most elegant and concise way that one JS file could print the ...
-1
votes
1
answer
524
views
Turing machines and decidability
It is known that there are decidable problems, semi-decidable problems, and undecidable problems. A language that is accepted by a TM (Turing Machine) is a r.e. set (recursively enumerable), and, in ...