[PDF] BBM401-Lecture 7: Decidable Languages and the Halting Problem





Previous PDF Next PDF



Solutions to Problem Set 4

Feb 23 2007 If. A is finite



CS 373: Theory of Computation

decidable (or simply decidable) if there exists a TM M which decides L. • Every finite language is decidable: For example by a TM that has all the strings in ...



A note on algebras of languages A note on algebras of languages

study some immunity properties: for instance we prove that for every coinfinite decidable language L there exists a decidable language L′ such that L ⊆ L′ L′ 



CSE 135: Introduction to Theory of Computation Decidability and

▷ Every finite language is decidable. Page 10. Decidable and Recognizable Languages. Recall: Definition. A Turing machine M is said to recognize a language L 



CSE 6321 - Solutions to Problem Set 1

Show that the collection of decidable languages is closed under the following operations. 1. complementation. Solution: Proof. Let L be a decidable language and 



Adriana Palacio - University of California San Diego Instructor

Jul 29 2004 Since all finite languages are regular



Practice Problems for Final Exam: Solutions CS 341: Foundations of

In each part below if you need to prove that the given language L is decidable



Lecture 33: Reductions and Undecidability SD & Turing Enumerable

• Can only happen if L is finite. • But all finite languages are decidable. • Fixes proof. • But not decidable whether L is finite!! Undecidable Problems. The 



Decidability

If any generate w accept





CS 373: Theory of Computation

Every finite language is decidable: For example by a TM that has all the Proposition 2. If L and L are recognizable



Solutions to Problem Set 4

23 févr. 2007 these machines only recognize regular languages). ... A is finite it is decidable because all finite languages are decidable (just hardwire ...



Practice Problems for Final Exam: Solutions CS 341: Foundations of

In each part below if you need to prove that the given language L is decidable



BBM401-Lecture 7: Decidable Languages and the Halting Problem

Every finite language is decidable: For e.g. by a TM that has Proposition. If L and L are recognizable



CMPE 350 - Spring 2018

26 avr. 2018 Prove or disprove: “The class of non-context-free languages is closed under com- ... decidable because all finite languages are decidable.



Languages and Finite Automata

Every decidable language is Turing-Acceptable a finite language? ... If a language is decidable then its complement is decidable too. L. L. Proof:.



Undecidability - Lecture in INF4130

18 oct. 2018 Theorem. Any finite language is decidable. Proof. If A is a finite language a decider MD for A can be constructed by hard-coding all.



Co-finiteness of VASS coverability languages

24 juil. 2019 and ?fin(A) to denote the set of all finite subsets of A. ... for VASS coverability languages is decidable. Proof. Consider finite sets of ...



CSE 6321 - Solutions to Problem Set 1

Show that the collection of decidable languages is closed under the following operations. 1. complementation. Solution: Proof. Let L be a decidable language and 



Equations over finite sets of words and equivalence problems in

a given regular language. L i.e. whether cr(.x)=t(.~) holds for all x in L

Lecturer: Lale Özkahya

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language ComplementationDecidable and Recognizable Languages

Recall: Definition

A Turing machineMis said torecognize a language LifL=L(M).A Turing machineMis said todecide a langua geLifL=L(M)

andMhalts on every input.Lis said to beT uring-recognizable(o rsimply recognizable) if there exists a TMMwhich recognizesL.Lis said to beT uring-decidable

(or simply decidable) if there exists a TMMwhich decidesL.Every finite language is decidable: For e.g., by a TM that has

all the strings in the language "hard-coded" into itWe just saw some example algorithms all of which terminate

in a finite number of steps, and output yes or no (accept or reject).i.e., They decide the corresponding languages.

Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language ComplementationDecidable and Recognizable Languages

Recall: Definition

A Turing machineMis said torecognize a language LifL=L(M).A Turing machineMis said todecide a langua geLifL=L(M)

andMhalts on every input.Lis said to beT uring-recognizable(o rsimply recognizable) if there exists a TMMwhich recognizesL.Lis said to beT uring-decidable

(or simply decidable) if there exists a TMMwhich decidesL.Every finite language is decidable: For e.g., by a TM that has

all the strings in the language "hard-coded" into itWe just saw some example algorithms all of which terminate

in a finite number of steps, and output yes or no (accept or reject).i.e., They decide the corresponding languages.

Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language ComplementationDecidable and Recognizable Languages

Recall: Definition

A Turing machineMis said torecognize a language LifL=L(M).A Turing machineMis said todecide a langua geLifL=L(M)

andMhalts on every input.Lis said to beT uring-recognizable(o rsimply recognizable) if there exists a TMMwhich recognizesL.Lis said to beT uring-decidable

(or simply decidable) if there exists a TMMwhich decidesL.Every finite language is decidable: For e.g., by a TM that has

all the strings in the language "hard-coded" into itWe just saw some example algorithms all of which terminate

in a finite number of steps, and output yes or no (accept or reject).i.e., They decide the corresponding languages.

Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language ComplementationDecidable and Recognizable Languages

Recall: Definition

A Turing machineMis said torecognize a language LifL=L(M).A Turing machineMis said todecide a langua geLifL=L(M)

andMhalts on every input.Lis said to beT uring-recognizable(o rsimply recognizable) if there exists a TMMwhich recognizesL.Lis said to beT uring-decidable

(or simply decidable) if there exists a TMMwhich decidesL.Every finite language is decidable: For e.g., by a TM that has

all the strings in the language "hard-coded" into itWe just saw some example algorithms all of which terminate

in a finite number of steps, and output yes or no (accept or reject).i.e., They decide the corresponding languages.

Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language ComplementationDecidable and Recognizable Languages

Recall: Definition

A Turing machineMis said torecognize a language LifL=L(M).A Turing machineMis said todecide a langua geLifL=L(M)

andMhalts on every input.Lis said to beT uring-recognizable(o rsimply recognizable) if there exists a TMMwhich recognizesL.Lis said to beT uring-decidable

(or simply decidable) if there exists a TMMwhich decidesL.Every finite language is decidable: For e.g., by a TM that has

all the strings in the language "hard-coded" into itWe just saw some example algorithms all of which terminate

in a finite number of steps, and output yes or no (accept or reject).i.e., They decide the corresponding languages.

Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language ComplementationDecidable and Recognizable Languages

Recall: Definition

A Turing machineMis said torecognize a language LifL=L(M).A Turing machineMis said todecide a langua geLifL=L(M)

andMhalts on every input.Lis said to beT uring-recognizable(o rsimply recognizable) if there exists a TMMwhich recognizesL.Lis said to beT uring-decidable

(or simply decidable) if there exists a TMMwhich decidesL.Every finite language is decidable: For e.g., by a TM that has

all the strings in the language "hard-coded" into itWe just saw some example algorithms all of which terminate

in a finite number of steps, and output yes or no (accept or reject).i.e., They decide the corresponding languages.

Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language ComplementationDecidable and Recognizable Languages

Recall: Definition

A Turing machineMis said torecognize a language LifL=L(M).A Turing machineMis said todecide a langua geLifL=L(M)

andMhalts on every input.Lis said to beT uring-recognizable(o rsimply recognizable) if there exists a TMMwhich recognizesL.Lis said to beT uring-decidable

(or simply decidable) if there exists a TMMwhich decidesL.Every finite language is decidable: For e.g., by a TM that has

all the strings in the language "hard-coded" into itWe just saw some example algorithms all of which terminate

in a finite number of steps, and output yes or no (accept or reject).i.e., They decide the corresponding languages.

Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language ComplementationDecidable and Recognizable Languages

Recall: Definition

A Turing machineMis said torecognize a language LifL=L(M).A Turing machineMis said todecide a langua geLifL=L(M)

andMhalts on every input.Lis said to beT uring-recognizable(o rsimply recognizable) if there exists a TMMwhich recognizesL.Lis said to beT uring-decidable

(or simply decidable) if there exists a TMMwhich decidesL.Every finite language is decidable: For e.g., by a TM that has

all the strings in the language "hard-coded" into itWe just saw some example algorithms all of which terminate

in a finite number of steps, and output yes or no (accept or reject).i.e., They decide the corresponding languages.

Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language ComplementationDecidable and Recognizable Languages But not all languages a redecidable !In the next class we will see an example:A tm={?M,w? |Mis a TM andMacceptsw}is undecidableHoweverAtmisT uring-recognizable!Proposition There are languages which are recognizable, but not decidable

Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language ComplementationDecidable and Recognizable Languages But not all languages a redecidable !In the next class we will see an example:A tm={?M,w? |Mis a TM andMacceptsw}is undecidableHoweverAtmisT uring-recognizable!Proposition There are languages which are recognizable, but not decidable

Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language ComplementationDecidable and Recognizable Languages But not all languages a redecidable !In the next class we will see an example:A tm={?M,w? |Mis a TM andMacceptsw}is undecidableHoweverAtmisT uring-recognizable!Proposition There are languages which are recognizable, but not decidable

Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language ComplementationDecidable and Recognizable Languages But not all languages a redecidable !In the next class we will see an example:A tm={?M,w? |Mis a TM andMacceptsw}is undecidableHoweverAtmisT uring-recognizable!Proposition There are languages which are recognizable, but not decidable

Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language

ComplementationRecognizingAtm

ProgramUforrec ognizingAtm:

On input?M,w?

simulateMonw if simulatedMacceptsw, then accept else reject (by moving toqrej)U(the Universal TM) accepts?M,w?iffMacceptsw. i.e., L(U) =AtmButUdoes notdecide Atm: IfMrejectswby not halting,U rejects?M,w?by not halting.Indeed (as we shall see) no TM decidesAtm.Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language

ComplementationRecognizingAtm

ProgramUforrec ognizingAtm:

On input?M,w?

simulateMonw if simulatedMacceptsw, then accept else reject (by moving toqrej)U(the Universal TM) accepts?M,w?iffMacceptsw. i.e., L(U) =AtmButUdoes notdecide Atm: IfMrejectswby not halting,U rejects?M,w?by not halting.Indeed (as we shall see) no TM decidesAtm.Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language

ComplementationRecognizingAtm

ProgramUforrec ognizingAtm:

On input?M,w?

simulateMonw if simulatedMacceptsw, then accept else reject (by moving toqrej)U(the Universal TM) accepts?M,w?iffMacceptsw. i.e., L(U) =AtmButUdoes notdecide Atm: IfMrejectswby not halting,U rejects?M,w?by not halting.Indeed (as we shall see) no TM decidesAtm.Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language

ComplementationRecognizingAtm

ProgramUforrec ognizingAtm:

On input?M,w?

simulateMonw if simulatedMacceptsw, then accept else reject (by moving toqrej)U(the Universal TM) accepts?M,w?iffMacceptsw. i.e., L(U) =AtmButUdoes notdecide Atm: IfMrejectswby not halting,U rejects?M,w?by not halting.Indeed (as we shall see) no TM decidesAtm.Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language

ComplementationRecognizingAtm

ProgramUforrec ognizingAtm:

On input?M,w?

simulateMonw if simulatedMacceptsw, then accept else reject (by moving toqrej)U(the Universal TM) accepts?M,w?iffMacceptsw. i.e., L(U) =AtmButUdoes notdecide Atm: IfMrejectswby not halting,U rejects?M,w?by not halting.Indeed (as we shall see) no TM decidesAtm.Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language

ComplementationDeciding vs. Recognizing

Proposition

If L andL are recognizable, then L is decidable

Proof.

ProgramPfordec idingL, given programsPLandPL

for recognizingLandL:On inputx, simulatePLandPL on inputx.Whetherx?Lor x??L, one ofPLandPL will halt in finite number of steps.Which one to simulate first?Either could go on forever.

On inputx, simulatein pa rallelPLandPL

on inputxuntil eitherPLorPL acceptsIfPLaccepts, acceptxand halt. IfPL accepts, rejectxand halt.··→Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language

ComplementationDeciding vs. Recognizing

Proposition

If L andL are recognizable, then L is decidable

Proof.

ProgramPfordec idingL, given programsPLandPL

for recognizingLandL:On inputx, simulatePLandPL on inputx.Whetherx?Lor x??L, one ofPLandPL will halt in finite number of steps.Which one to simulate first?Either could go on forever.

On inputx, simulatein pa rallelPLandPL

on inputxuntil eitherPLorPL acceptsIfPLaccepts, acceptxand halt. IfPL accepts, rejectxand halt.··→Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language

ComplementationDeciding vs. Recognizing

Proposition

If L andL are recognizable, then L is decidable

Proof.

ProgramPfordec idingL, given programsPLandPL

for recognizingLandL:On inputx, simulatePLandPL on inputx.Whetherx?Lor x??L, one ofPLandPL will halt in finite number of steps.Which one to simulate first?Either could go on forever.

On inputx, simulatein pa rallelPLandPL

on inputxuntil eitherPLorPL acceptsIfPLaccepts, acceptxand halt. IfPL accepts, rejectxand halt.··→Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language

ComplementationDeciding vs. Recognizing

Proposition

If L andL are recognizable, then L is decidable

Proof.

ProgramPfordec idingL, given programsPLandPL

for recognizingLandL:On inputx, simulatePLandPL on inputx.Whetherx?Lor x??L, one ofPLandPL will halt in finite number of steps.Which one to simulate first?Either could go on forever.

On inputx, simulatein pa rallelPLandPL

on inputxuntil eitherPLorPL acceptsIfPLaccepts, acceptxand halt. IfPL accepts, rejectxand halt.··→Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language

ComplementationDeciding vs. Recognizing

Proposition

If L andL are recognizable, then L is decidable

Proof.

ProgramPfordec idingL, given programsPLandPL

for recognizingLandL:On inputx, simulatePLandPL on inputx.Whetherx?Lor x??L, one ofPLandPL will halt in finite number of steps.Which one to simulate first?Either could go on forever.

On inputx, simulatein pa rallelPLandPL

on inputxuntil eitherPLorPL acceptsIfPLaccepts, acceptxand halt. IfPL accepts, rejectxand halt.··→Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language

ComplementationDeciding vs. Recognizing

Proposition

If L andL are recognizable, then L is decidable

Proof.

ProgramPfordec idingL, given programsPLandPL

for recognizingLandL:On inputx, simulatePLandPL on inputx.Whetherx?Lor x??L, one ofPLandPL will halt in finite number of steps.Which one to simulate first?Either could go on forever.

On inputx, simulatein pa rallelPLandPL

on inputxuntil eitherPLorPL acceptsIfPLaccepts, acceptxand halt. IfPL accepts, rejectxand halt.··→Agha-ViswanathanCS373

High-Level Descriptions of Computation

Deciding vs. Recognizing

Recursive EnumerationAn Undecidable but Recognizable Language

ComplementationDeciding vs. Recognizing

Proof (contd).

In more detail,Pworks as follows:

On input x

fori= 1,2,3,... simulatePLon inputxforisteps simulatePL on inputxforisteps if either simulation accepts, break ifPLaccepted, acceptx(and halt)quotesdbs_dbs22.pdfusesText_28
[PDF] all font types list

[PDF] all fonts family css

[PDF] all fonts name list

[PDF] all fonts supported in html

[PDF] all fonts that can be used in html

[PDF] all formula of solution chapter

[PDF] all formulas of chapter 2 chemistry class 11

[PDF] all formulas of chemical kinetics class 12

[PDF] all formulas of electrochemistry

[PDF] all formulas of electrochemistry class 12

[PDF] all formulas of solutions class 12 chemistry

[PDF] all formulas of statistics class 10th

[PDF] all formulas of statistics class 11

[PDF] all formulas of statistics class 11 economics

[PDF] all formulas of statistics class 11 maths