Если множество неперечислимо, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции
.RU

Если множество неперечислимо, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции


Если множество неперечислимо, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции

  1. может быть, может быть

  2. может быть, не может быть

  3. не может быть, не может быть

  4. не может быть, может быть

  • В любой рекурсивно аксиоматизированной формальной системе множество доказуемых утверждений

    1. рекурсивно перечислимо

    2. неперечислимо

    3. нерекурсивно

    4. разрешимо

  • Функция, вычислимая по Тьюрингу, является

    1. примитивно рекурсивной

    2. общерекурсивной

    3. характеристической

    4. частично рекурсивной

  • Функция имеет Гёделевский номер, равный

    1. 2

    2. 4

    3. 3

    4. 1

  • Функция является: 1) частично вычислимой; 2) примитивно рекурсивной; 3) частично рекурсивной

    1. 1 и 2

    2. 1

    3. 1 и 3

    4. 2 и 3

  • Частично вычислимая функция

    1. может быть продолжена до вычислимой

    2. это частный случай вычислимой

    3. не везде совпадает с вычислимой

    4. вычисляется с ограниченной точностью

  • Пусть R – рекурсивность, а P – рекурсивная перечислимость. Тогда









  • Входной алфавит определяется как









  • Если и рекурсия проводится по переменной , то функция равна

    1. m+y

    2. 1

    3. m+x



  • Команда машины Тьюринга состоит из элементарных действий

    1. любого числа

    2. двух

    3. трех

    4. конечного числа

  • Утверждение арифметики Пеано называется неразрешенным, если оно

    1. и его отрицание -противоречивы

    2. истинно, но недоказуемо

    3. и его отрицание опровержимы

    4. противоречит системе аксиом

  • Теория алгоритмов является частью

    1. математического анализа

    2. численных методов

    3. математической логики

    4. теории чисел

  • Усеченная разность равна

    1. 3

    2. -3

    3. 5

    4. 0

  • Всякая вычислимая функция является вычислимой по Тьюрингу согласно

    1. лемме Тьюринга

    2. тезису Чёрча

    3. теореме Поста

    4. теореме Гёделя

  • Если множество не является множеством значений никакой функции, то оно

    1. рекурсивно, но не перечислимо

    2. нерекурсивно, но рекурсивно перечислимо

    3. рекурсивно, но не перечислимо

    4. нерекурсивно и неперечислимо

  • Если , то функция в рекуррентной формуле равна



    1. sin(πn)



    2. m+1

  • Если и рекурсия проводится по переменной , то функция равна

    1. y+1

    2. x

    3. x+1

    4. y

  • Функция является

    1. частично вычислимой

    2. рекурсивной

    3. общерекурсивной

    4. вычислимой

  • Теорема, связывающая рекурсивности множества с рекурсивной перечислимостью этого множества и его дополнения, называется теоремой

    1. Тьюринга

    2. Клини

    3. Гёделя

    4. Поста

  • Функция является примитивно рекурсивной, если она получается из набора исходных функций с помощью оператора: 1) рекурсии; 2) ограниченной минимизации; 3) подстановки – из перечисленного

    1. 1

    2. 1, 2 и 3

    3. 1 и 2

    4. 1 и 3

  • Каждая п.р.ф имеет число номеров

    1. индивидуальное

    2. бесконечное

    3. ограниченное

    4. небольшое

  • Дополнение к области определения некоторой вычислимой функции _________ рекурсивно перечислимым

    1. разъединено с

    2. должно быть

    3. может не быть

  • не может быть Геделевский номер, равный 23, имеет функция

    1. S(S(x))







  • Осмысленные конечные последовательности символов из алфавита L называются

    1. утверждениями

    2. словарем

    3. командами

    4. программой

  • Множество составных чисел является

    1. порождающим

    2. рекурсивным и перечислимым

    3. только перечислимым

    4. только рекурсивным

  • Если и рекурсия проводится по переменной , то функция равна

    1. m+y



    2. m+x

    3. 1

  • В рекурсивно аксиоматизированной формальной системе, в которой все доказуемые утверждения истинны, существует истинное утверждение , так что: 1)  опровержимо; 2)  опровержимо

    1. 2

    2. ни 1, ни 2

    3. 1

    4. 1 и 2

  • Утверждение формально записывается как









  • Если и рекурсия проводится по переменной , то функция равна

    1. ty





    2. t+x+y+z

  • Если и рекурсия проводится по , то функция равна









  • Не существует формальной системы арифметики, удовлетворяющей условиям полноты и противоречивости согласно

    1. теореме Поста

    2. тезису Черча

    3. теории Гильберта

    4. теореме Геделя

  • Марковский алгоритм – это алгоритм

    1. недетерминированный

    2. стохастический

    3. нормальный

    4. нелинейный

  • Формальная грамматика, позволяющая построить любую правильную цепочку символов, называется грамматикой

    1. автоматной

    2. порождающей

    3. нормальной

    4. регулярной

  • Функция, равная единице тогда и только тогда, когда предикат истинен, называется

    1. характеристической

    2. примитивно вычислимой

    3. вычислимой

    4. частично рекурсивной

  • Если и рекурсия проводится по , то функция равна

    1. zy







  • Функция вычисляется по формуле









  • Входят в алфавит формального логического языка символы









  • Класс примитивно рекурсивных функций

    1. входит в класс вычислимых функций

    2. совпадает с классом вычислимых функций

    3. содержит в себе класс вычислимых функций

    4. расширяет класс вычислимых функций

  • Каждая п.р.ф имеет число номеров

    1. небольшое

    2. бесконечное

    3. индивидуальное

    4. ограниченное

  • Символы, которые машина Тьюринга читает и пишет на ленте, образуют

    1. выражения

    2. алфавит

    3. команды

    4. конфигурацию

  • Функция, полученная из вычислимой с помощью рекурсии, является

    1. примитивно рекурсивной

    2. дифференцируемой

    3. частично рекурсивной

    4. вычислимой

  • Конечное множество команд, имеющих попарно различные начальные пары символов, называется

    1. алгоритмом

    2. машиной Тьюринга

    3. программой

    4. конфигурацией

  • Функция имеет Гёделевский номер, равный

    1. 4

    2. 2

    3. 3

    4. 1

  • Если множество рекурсивно, то оно является ______ всюду определенной вычислимой функции

    1. только множеством значений

    2. только областью определения

    3. ни множеством значений, ни областью определения

    4. множеством значений и областью определения

  • Если и рекурсия проводится по , то функция равна



    1. x+z

    2. 0



  • Формализованный язык для однозначной записи алгоритмов называется

    1. автоматным языком

    2. алгоритмическим языком

    3. регулярным языком

    4. метаязыком языком

  • Пусть R – рекурсивность, а P – рекурсивная перечислимость. Тогда









  • Временные или пространственные характеристики процесса вычисления называются

    1. классом сложности

    2. интерпретацией системы

    3. вычислительными ресурсами

    4. представлением системы

  • Если и рекурсия проводится по , то функция равна









  • Машина Тьюринга есть совокупность компонент

    1. трех

    2. пяти

    3. двух

    4. четырех

  • Множество доказуемых утверждений формальной системы арифметики

    1. открыто

    2. разрешимо

    3. замкнуто

    4. неразрешимо

  • Композиция и равна







    1. 1

  • Всякое непустое ______ множество является _________ некоторой всюду определенной вычислимой функции

    1. рекурсивно перечислимое, множеством значений

    2. креативное, областью определения

    3. рекурсивное, областью определения

    4. продуктивное, множеством значений

  • Функция называется частично рекурсивной, если она либо принадлежит к числу исходных п.р.ф., либо может быть получена из них с помощью операторов

    1. подстановки, рекурсии

    2. рекурсии

    3. подстановки, рекурсии, минимизации

    4. подстановки, минимизации

  • Установление соответствия между элементарными высказываниями формальной теории и содержательными высказываниями некоторой предметной области называется

    1. интерпретацией теории

    2. классом функторов

    3. эффективной процедурой

    4. порождающей грамматикой

  • Полнота – это условие, что для любого утверждения  одно из утверждений  и 

    1. истинно

    2. опровержимо

    3. доказуемо

    4. ложно

  • Множество истинных утверждений

    1. носит название системы аксиом

    2. не выводится из системы аксиом

    3. перечисляет все системы аксиом

    4. выводится из системы аксиом

  • Множество простых чисел является

    1. рекурсивным и перечислимым

    2. только перечислимым

    3. только рекурсивным

  • замкнутым Если и рекурсия проводится по переменной , то функция равна



    1. t+x+y+z



    2. ty

  • Язык, на котором описывается другой язык, называется

    1. формулой языка Ъ

    2. формальной системой

    3. автоматным языком

    4. метаязыком

  • Показал возможность существования универсальной вычислительной машины, способной выполнить любую эффективную процедуру

    1. А. Тьюринг

    2. К. Гёдель

    3. Д. Гильберт

    4. А. Марков

  • Марковский алгоритм – это алгоритм

    1. нормальный

    2. стохастический

    3. нелинейный

    4. недетерминированный

  • Если и рекурсия проводится по переменной , то функция равна









  • Если , то функция в рекуррентной формуле равна

    1. m+1

    2. m+n+1

    3. m(n+1)

    4. m!

  • Множество номеров самоприменимых машин Тьюринга

    1. рекурсивно перечислимо, но не разрешимо

    2. неперечислимо, но разрешимо

    3. рекурсивно перечислимо и разрешимо

    4. ни перечислимо, ни разрешимо

  • Если и рекурсия проводится по , то функция равна

    1. 1



    2. 0



  • Внутренним алфавитом машины Тьюринга называется

    1. множество конфигураций машины

    2. множеством состояний машины

    3. множество команд машины

    4. символы, записанные на ленте

  • Если A и B – рекурсивные множества, то рекурсивны также множества
    I.
    II.
    III.

    1. I, II и III

    2. только I и III

    3. только II

    4. только I и II

  • Функция имеет гёделевский номер, равный

    1. 9

    2. 3

    3. 13

    4. 19

  • Функция является: 1) частично вычислимой; 2) примитивно рекурсивной; 3) частично рекурсивной

    1. 1 и 2

    2. 2 и 3

    3. 1 и 3

    4. 1

  • Функция, вычисляемая некоторой машиной Тьюринга с входным и выходным алфавитами, называется

    1. обратной

    2. характеристической

    3. вычислимой

    4. рекурсивной

  • Конечному автомату соответствует грамматика, порождающая

    1. регулярный язык

    2. язык программирования

    3. машину Тьюринга

    4. словарь машины

  • Если множество нерекурсивно, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции

    1. не может быть, может быть

    2. не может быть, не может быть

    3. может быть, не может быть

    4. может быть, может быть

  • Если и рекурсия проводится по переменной , то функция равна

    1. 2+m

    2. m+1

    3. m+y

    4. m+x

  • Множество составных чисел является

    1. только перечислимым

    2. только рекурсивным

    3. порождающим

    4. рекурсивным и перечислимым

  • Теория алгоритмов является частью

    1. численных методов

    2. математической логики

    3. математического анализа

    4. теории чисел

  • Множество натуральных чисел является

    1. рекурсивным и перечислимым

    2. только перечислимым

    3. простейшим

    4. только рекурсивным

  • Если , то функция (n,m) в рекуррентной формуле равна

    1. m+n+1

    2. (m+n)/2

    3. m+n-1

    4. 2m

  • Функция является

    1. вычислимой

    2. частично вычислимой

    3. общерекурсивной

    4. рекурсивной

  • Если , то функция в рекуррентной формуле равна







    1. 1

  • Утверждение арифметики Пеано называется неразрешенным, если оно

    1. противоречит системе аксиом

    2. истинно, но недоказуемо

    3. и его отрицание -противоречивы

    4. и его отрицание опровержимы

  • Символы, которые машина Тьюринга читает и пишет на ленте, образуют

    1. алфавит

    2. конфигурацию

    3. команды

    4. выражения

  • Конечное множество команд, имеющих попарно различные начальные пары символов, называется

    1. конфигурацией

    2. машиной Тьюринга

    3. программой

    4. алгоритмом

  • Функция, определяемая как число шагов в вычислении машиной Тьюринга, называется

    1. характеристической

    2. геделевским номером

    3. длиной программы

    4. временным ресурсом

  • Функция имеет гёделевский номер, равный

    1. 2

    2. 1

    3. 4

    4. 5

  • Геделевский номер, равный , имеет функция









  • Полнота – это условие, что для любого утверждения  одно из утверждений  и 

    1. доказуемо

    2. опровержимо

    3. истинно

    4. ложно

  • Функция равна

    1. xyz

    2. x+y

    3. x+y+z

    4. 3

  • Если и рекурсия проводится по , то функция равна





    1. t+y

    2. t+x

  • Множество всех истинных утверждений языка L является

    1. разрешимым и перечислимым

    2. неразрешимым, но перечислимым

    3. неразрешимым и неперечислимым

    4. разрешимым, но неперечислимым

  • В любой рекурсивно аксиоматизированной формальной системе множество доказуемых утверждений

    1. рекурсивно перечислимо

    2. разрешимо

    3. нерекурсивно

    4. неперечислимо

  • Композиция и равна



    1. 1





  • Формализованный язык для однозначной записи алгоритмов называется

    1. автоматным языком

    2. алгоритмическим языком

    3. метаязыком языком

    4. регулярным языком

  • Функция имеет Гёделевский номер, равный

    1. 4

    2. 1

    3. 3

    4. 2







    etnodemograficheskij-sostav-i-chislennost-naseleniya-abhazii-pomaterialam-statisticheskih-issledovanijprovodimih-v-raznie-periodi.html
    etnogenez-i-biosfera-zemli.html
    etnogeograficheskoe-polozhenie-rossii.html
    etnograficheskie-priemi-v-marketingovih-issledovaniyah-chast-3.html
    etnografiya-detstva-chuvashej-volgo-uralya-vo-vtoroj-polovine-xix-pervoj-treti-xx-vv-tradicionnaya-rodilnaya-obryadnost-i-socializaciya-rebenka.html
    etnografiya-narodov-rossii-rabochie-programmi-cikla-obshih-gumanitarnih-i-socialno-ekonomicheskih-disciplin-anglijskij.html
  • writing.bystrickaya.ru/dlya-studentov-dnevnoj-formi-obucheniya-uchebnaya-programma-dlya-specialnosti-1-24-01-01-mezhdunarodnoe-pravo.html
  • desk.bystrickaya.ru/platonovskie-chteniya-materiali-xiii-vserossijskoj-konferencii-molodih-istorikov-g-samara-23-24-noyabrya-2007-g-samara-izdatelstvo-univers-grupp-2007.html
  • institute.bystrickaya.ru/glava-30-akcii-planshe-i-k-podnimayutsya-vikont-de-brazhelon-ili-desyat-let-spustya.html
  • school.bystrickaya.ru/doklad-rabochej-gruppi-specialnomu-komitetu-stranica-4.html
  • institute.bystrickaya.ru/glava-1-obshie-polozheniya-kompleksnie-meri-profilaktiki-zloupotrebleniya-narkoticheskimi-sredstvami-i-psihotropnimi.html
  • learn.bystrickaya.ru/glava-vii-oplata-truda-zakonodatelstva-o-trude.html
  • student.bystrickaya.ru/3-kompetencii-formiruemie-v-rezultate-osvoeniya-disciplini-annotacii-disciplin-oop-bakalavriata-politologiya.html
  • laboratory.bystrickaya.ru/vozbuzhdenie-proizvodstva-po-peresmotru-sudebnogo-postanovleniya-v-poryadke-nadzora-i-processualnij-poryadok-rassmotreniya-protestov-chast-5.html
  • knowledge.bystrickaya.ru/obrazovatelnij-standart-realizacii-programm-visshego-professionalnogo-obrazovaniya-sankt-peterburgskogo-gosudarstvennogo-stranica-2.html
  • student.bystrickaya.ru/3-effektivnaya-organizaciya-fizkulturno-ozdorovitelnoj-raboti-prikaz-ot-25-05-2011-g-osnovnaya-obrazovatelnaya.html
  • occupation.bystrickaya.ru/obrabotka-100-sluchajno-vibrannih-pisem-v-den-ya-hvatit-rabotat-sverhurochno-pora-rabotat-racionalno-dlya.html
  • lektsiya.bystrickaya.ru/programma-disciplini-filosofiya-gse-f-10-specialnost-teoriya-i-metodika-prepodavaniya-inostrannih-yazikov-i-kultur-022600-031201-65-obshie-celi-i-zadachi-kursa-kurs-filosofiya.html
  • knigi.bystrickaya.ru/sovremennoe-sostoyanie-i-tendencii-razvitiya-mezhdunarodnogo-i-mezhregionalnogo-sotrudnichestva-krasnodarskogo-kraya-stranica-2.html
  • prepodavatel.bystrickaya.ru/strahovie-dokumenti-v-ved.html
  • report.bystrickaya.ru/istoriya-razvitiya-psihologicheskogo-znaniya-i-osnovnie-napravleniya-v-psihologii.html
  • lecture.bystrickaya.ru/aktualnie-voprosi-nejrobiologii-nejroinformatiki-i-kognitivnih-issledovanij.html
  • thescience.bystrickaya.ru/istoriya-religii-i-cerkvi-itogi-tretego-regionalnogo-zaochnogo-etapa-konkursa-nauchnih-proektov-shkolnikov-v.html
  • kolledzh.bystrickaya.ru/a-t-fomenko-i-g-v-nosovskogo-stranica-12.html
  • turn.bystrickaya.ru/osobennosti-podgotovki-proektov-prikazov-komandirov-nachalnikov-po-rezultatam-hozyajstvennoj-deyatelnosti-osushestvlyaemoj-podchinennimi-im-voinskimi-chastyami1.html
  • vospitanie.bystrickaya.ru/zanyatie-26-latinskij-yazik.html
  • gramota.bystrickaya.ru/znaki-prepinaniya-v-slozhnosochinennih-predlozheniyah-ssp-kak-podgotovitsya-k-sdache-ekzamenov-podgotovka-k-ekzamenu.html
  • doklad.bystrickaya.ru/v-a-barketov-klirik-saratovskoj-mitropolii-russkoj-pravoslavnoj-cerkvi.html
  • esse.bystrickaya.ru/punktuacionnie-kazusi-ili.html
  • vospitanie.bystrickaya.ru/zapozdalaya-likvidnost-sessiya-parlamentskogo-sobraniya-soyuza-rossii-i-belorussii-11.html
  • studies.bystrickaya.ru/marketing-uslug-5.html
  • university.bystrickaya.ru/glava-6-dengi-tomas-vuds.html
  • occupation.bystrickaya.ru/moskva-stranica-6.html
  • books.bystrickaya.ru/dohodi-byudzhetov-za-2009-g-fakt-2010-g-plan-goroda-sibiri-i-dalnego-vostoka-gruppa-2.html
  • studies.bystrickaya.ru/kompensaciya-reaktivnoj-moshnosti.html
  • control.bystrickaya.ru/dvenadcat-lekcij-prochitannih-v-dornahe-s-19-oktyabrya-po-11-noyabrya-1923-goda-perevod-s-nemeckogo-s.html
  • testyi.bystrickaya.ru/administrativno-pravovoj-status-obshestvennih-obedinenij-chast-7.html
  • grade.bystrickaya.ru/mukutadze-murman-alexandrovich-issledovanie-fiziko-himicheskih.html
  • university.bystrickaya.ru/glava-5-sostavlenie-plana-podvodnogo-uchastka-dzhorzh-bass-podvodnaya-arheologiya.html
  • institut.bystrickaya.ru/tehnologiya---1156-federalnij-perechen-uchebnikov.html
  • report.bystrickaya.ru/gsd-grubij-selsin-datchik-rabochaya-programma-metodicheskie-ukazaniya-i-kontrolnie-zadaniya-dlya-studentov-specialnosti.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.