/sci/ - Science & Math » Thread #13662159

107KiB, 1080x1350, je.jpg

View Same Google iqdb SauceNAO

computability

Anonymous Mon 20 Sep 11:20:52 2021 No.13662159 View Reply Original Report

Quoted By: >>13662218 >>13664523 >>13664912 >>13665688

From what I understand, a turing machine or a automata is supposed to decide or recognize a language, which generated by a grammar. If computers are turing machines then what are languages? How concepts like recognize or decide can be translated to real life?

Anonymous

Anonymous Mon 20 Sep 2021 11:52:04 No.13662218 Report

Quoted By: >>13662293

>>13662159
In automata theory, they're called languages because the things the automaton scans are "words" (finite sequences) of symbols from an "alphabet" (a set). Turing machines, on the other hand, are a lot more powerful and flexible, so when working with them you usually use different terms.
>not "words" but numbers $n \in \mathbb{N}$
>not "languages" but "problems" $A \subseteq \mathbb{N}$
For example the "halting problem" is the set $\{n \in \mathbb{N} :$ Turing machine #n eventually halts $\}$ . This "problem" is recognizable (by Turing machine) but not decidable (by Turing machine).
>How concepts like recognize or decide can be translated to real life?
Say you have a checklist of the people you might meet today. Recognizing the correct list is like going through the day and checking off the people you do meet. Deciding the list is like putting checks in all the right places before you even go out: a much harder task.

Anonymous

Anonymous Mon 20 Sep 2021 12:30:57 No.13662293 Report

Quoted By:

>>13662218
>Say you have a checklist of the people you might meet today. Recognizing the correct list is like going through the day and checking off the people you do meet. Deciding the list is like putting checks in all the right places before you even go out: a much harder task.
Didn't make much sense at first but I kinda get it now, if you can decides the list then you can checks the list before even go out

Anonymous

Anonymous Tue 21 Sep 2021 00:20:21 No.13664523 Report

Quoted By:

>>13662159
>If computers are turing machines
Computers are *technically* weaker than Turing machines due to bounded space, but it doesn't matter for any problems we want to solve in practice.
> then what are languages
Languages are a way of formulating certain computational problems. It's a quick exercise to verify the following that every algorithmic task T you can define for a Turing Machine has a equivalent reformulation as a decision problem on a set of strings over {0, 1}^*
Note: most elementary problems are solved and we study computability and complexity with more complicated constructions for which the simple language formulation is too messy, ie look at this https://arxiv.org/abs/2109.07125

Anonymous

Anonymous Tue 21 Sep 2021 02:50:15 No.13664912 Report

Quoted By: >>13665688

>>13662159
Who's the girl?

Anonymous

Anonymous Tue 21 Sep 2021 10:05:35 No.13665688 Report

Quoted By:

>>13662159
Answer me >>13664912

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches