/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Problem 14 Show that every infinite recursi... [FREE SOLUTION] | 91影视

91影视

Log out

Learning Materials

Features

Discover

Chapter 5: Problem 14

Show that every infinite recursively enumerable set includes an infinite recursive set.

Short Answer

Expert verified
The proof is based on the definitions of recursively enumerable sets and recursive sets. By selecting an element from an infinite recursively enumerable set and forming a new set with this element and all elements less than it in the original set, an infinite recursive set can be created. This set is infinite because the original set is infinite, and it is recursive because membership in the set can be decided by a halting (terminating) algorithm

Step by step solution

01

Understand Recursively Enumerable Sets

A recursively enumerable set (or semidecidable set) is a set for which there exists a algorithm that will halt and output 'yes' if the input is in the set, and will run forever (or halt with 'no') if the input is not in the set.
02

Understand Recursive Sets

A recursive set (or decidable set) is a set for which there exists an algorithm that will halt and tell whether any given input is in the set or not, that is, it always halts with a 'yes' or 'no' answer.
03

Show that an Infinite Recursive Set is in an Infinite Recursively Enumerable Set

Let the infinite recursively enumerable set be \( S \). Now, we pick an element \( x \) from \( S \), and we can form a recursive set \( T \) that contains this element \( x \) and everything in the set \( S \) that is less than \( x \). This set \( T \) is infinite because \( S \) is infinite, and it is recursive because you can decide whether an element is in \( T \) by checking if it is less than \( x \) and in \( S \), which can be done by a halting algorithm due to the properties of \( S \). Hence, we have proved that every infinite recursively enumerable set includes an infinite recursive set.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91影视!

Key Concepts

These are the key concepts you need to understand to accurately answer the question.

Recursive Sets
In computational theory, a recursive set plays a central role in understanding what problems can be solved by a computer. Essentially, a recursive set is one where there is a definitive method to check whether any given element is a member of the set or not. This method, known as an algorithm, can be thought of as a computer program that will always give you an answer. For any input you provide, it will run for a while and then stop with a clear 'yes' or 'no' to tell you if that input is part of the set. This is the hallmark of decidability鈥攁 problem that can be decided, hence the alternate name, decidable set.

For instance, consider the set of all even numbers. We can create an algorithm that takes a number, divides it by two, and checks if there is a remainder. If there isn't, the number is even, thus part of our set; if there is, it's not. This process will conclude with an answer for any number, illustrating that the set of all even numbers is a recursive set.
Algorithms for Sets
When we talk about algorithms for sets, we're discussing a computational recipe that allows us to work with sets effectively. An algorithm for a set operates to determine membership, but beyond that, it can also construct a set, enumerate its elements, or perform operations such as union, intersection, and difference between sets.

Consider developing an algorithm for the set of prime numbers. This algorithm would need to ascertain whether any given number is prime. To do this, it could iterate from 2 to the square root of the number, attempting to divide the number in question. If it finds a divisor, the number isn't prime; if it finishes without any divisors, it is prime. Algorithms for sets can get quite complex when working with sets that are not easily definable or when the operations involve intricate structures or properties.
The Halting Problem
The halting problem is a fundamental concept in computer science and relates to the decidability of problems. Introduced by Alan Turing in 1936, the halting problem asks whether an algorithm can be written that decides whether any arbitrary program on a computer will eventually stop ('halt') or continue to run indefinitely.

Through a logical argument, Turing demonstrated that no such algorithm exists; that is, there's no general way to look at a piece of code and an input and predict whether the code will halt when run with that input. This result shows there are limits to what can be computed; not all problems are solvable. The relationship between the halting problem and recursive sets is that while recursive sets are always solvable (you can decide membership), not all sets are recursive, precisely because of this halting problem.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

When we constructed the functions \(\phi^{p}\), we used a certain number of codings and, for this purpose, we had to make some completely arbitrary choices. In this exercise, our concern is to know what sort of functions would have been obtained instead of the \(\phi^{p}\) if our choices had been different. The only assumption we will make is that these choices are reasonable and sufficient for proving the enumeration theorem and the fixed point theorems. Let \(\Psi=\left\\{\psi^{p}: p \geq 1\right\\}\) be a family of partial recursive functions such that, for all \(p, \psi^{p} \in \mathcal{F}_{p+1}^{*}\). We set $$ \psi_{x}^{p}=\lambda y_{1} y_{2} \ldots y_{p} . \psi^{p}\left(x, y_{1}, y_{2}, \ldots, y_{p}\right) . $$ Consider the following conditions on the family \(\Psi\) : -(enu) For every \(p>0\), the set \(\left\\{\psi_{i}^{p}: i \in \mathbb{N}\right\\}\) is equal to the set of all partial recursive functions of \(p\) variables. \- (smn) For every pair of integers \(m\) and \(n\), there exists a total recursive function \(\sigma_{n}^{m}\) of \(n+1\) variables such that for all \(i, x_{1}, x_{2}, \ldots, x_{n}, y_{1}, y_{2}, \ldots, y_{m}\), we have $$ \begin{aligned} &\psi^{n+m}\left(i, x_{1}, x_{2}, \ldots, x_{n}, y_{1}, y_{2} \ldots, y_{m}\right) \\ &\quad=\psi^{m}\left(\sigma_{n}^{m}\left(i, x_{1}, x_{2}, \ldots, x_{n}\right), y_{1}, y_{2}, \ldots, y_{m}\right) \end{aligned} $$ (a) Let \(\theta\) be a partial recursive function of two variables. For every integer \(x\), we \(\operatorname{set} \theta_{x}=\lambda y . \theta(x, y)\). Show that the following two conditions are equivalent: (i) there exists a family \(\Psi=\left\\{\psi^{p}: p \geq 1\right\\}\) that satisfies conditions (enu) and \((\mathrm{smn})\) and is such that \(\psi^{1}=\theta\); (ii) there exists a recursive function \(\beta\) such that, for all \(x, \phi_{x}^{1}=\theta_{\beta(x)}\). (b) Assume once more that the family \(\Psi\) satisfies the conditions (enu) and \((\mathrm{smn})\). Show that the fixed point theorems are valid for the family \(\Psi\). (c) Assume that the function \(\theta\) satisfies conditions (i) or (ii) from (a). Show that there exist two injective recursive functions \(\alpha\) and \(\beta\) such that, for all \(x\), $$ \phi_{x}^{1}=\theta_{\beta(x)} \quad \text { and } \quad \theta_{x}=\phi_{\alpha(x)}^{1} $$ (d) (Difficult!) Under these same hypotheses, show that there exists a recursive function \(\varepsilon\) that is total and bijective and is such that, for all \(x, \phi_{x}^{1}=\theta_{\varepsilon(x)}\).

Let \(\alpha\) be a recursive function that is injective. We set $$ \begin{aligned} &A=\operatorname{Ran}(\alpha) \\ &B=\\{x: \text { there exists } y>x \text { such that } \alpha(y)<\alpha(x)\\} \end{aligned} $$ (a) Show that \(B\) is recursively enumerable and that its complement is infinite. (b) Assume that there exists an infinite recursively enumerable subset \(C \subset \mathbb{N}\) that is disjoint from \(B\). Show that \(A\) is recursive. (c) Show that there exists a recursively enumerable set which has (1) a nonempty intersection with every infinite recursively enumerable set, and (2) an infinite complement.

(a) Show that the set of recursive bijections from \(\mathbb{N}\) onto \(\mathbb{N}\) is a subgroup of the group of permutations of \(\mathbb{N}\). The remainder of this exercise is devoted to showing that this assertion is false if we replace recursive by primitive recursive. (b) Let \(\phi\) be a (total) function of one variable that is recursive but not primitive recursive; let \(e\) be an index for a machine \(\mathcal{M}\) that computes \(\phi\). Consider the function \(T\) which associates, with \(x\), the time required by \(\mathcal{M}\) to compute \(\phi(x) ;\) more precisely, \(\left.T(x)=\mu t\left[(e, t, x) \in B^{1}\right)\right]\). Show that if \(f\) is a function that satisfies \(f(x) \geq T(x)\) for all \(x \in \mathbb{N}\), then \(f\) is not primitive recursive; also show that the graph \(G\) of \(T\) is primitive recursive. (c) We set $$ g(x)=\sup \\{T(y): y \leq x\\}+2 x . $$ Show that \(g\) is a strictly increasing recursive function and that it is not primitive recursive. Show that the graph \(G_{1}\) and the range \(I\) of \(g\) are primitive recursive sets. (d) Show that there is a unique strictly increasing primitive recursive function \(g^{\prime}\) whose range is the complement of \(I\). (e) Define the function \(h\) by $$ \begin{aligned} h(2 x) &=g(x) \\ h(2 x+1) &=g^{\prime}(x) \end{aligned} $$ where \(g\) and \(g^{\prime}\) are the functions defined in (c) and (d) above. Show that \(h\) is a bijective recursive function that is not primitive recursive. Show that its inverse, \(h^{-1}\), is primitive recursive.

Construct a Turing machine that halts if and only if the integer represented on its first band at the initial instant is even.

Let \(A \subseteq \mathbb{N}\) be a recursively enumerable set that is not recursive; let \(f\) be a partial recursive function whose domain is \(A\) and let \(i\) be an index for a Turing machine that computes \(f\). Show that the function \(\lambda x \cdot T^{1}(i, x)\) cannot be extended to a total recursive function [here, \(T^{1}\) is the function defined in the proof of the enumeration theorem whose value is the time required to compute \(f(x)\) ].
See all solutions

Recommended explanations on Math Textbooks

Pure Maths

Read Explanation

Geometry

Read Explanation

Applied Mathematics

Read Explanation

Calculus

Read Explanation

Mechanics Maths

Read Explanation

Probability and Statistics

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.