Цялостност по Тюринг: Разлика между версии
Изтрито е съдържание Добавено е съдържание
Ред 8:
{{copyvio}}
== История ==
Цялостност по Тюринг е значителен в
Аналитичния двигател на [[Чарлз Бабидж]] (1837) щеше да бъде първата Тюринг-пълна машина, ако тя е била построена по времето, когато е била проектирана. Бабидж оценява, че машината е в състояние на великите подвизи на изчисление, включително примитивно логическо мислене, но той не е преценил, че няма друга машина която може да се справи по-добре. От 1830 до 1940 г., механични изчислителни машини, като например разширители и мултипликатори са били построени и подобрени, но те не могат да изпълняват условния преход и следователно не бяха Тюринг пълни.
В края на 19 век, Леополд Кронекер формулира идеи за
Действителната идея за изчисление е изолирана скоро след, като се започне с непълната теорема на Гьодел. Тази теорема показва, че аксиома системите са ограничени, когато размишляването за изчислението, което намалява техните теореми.”Church” и Тюринг независимо показва това, че проблемът на Hilbert's Entscheidungs е нерешим, като по този начин се идентифицира изчислителната сърцевина, на непълната теорема. Това работи, дълго със работата на Гьодел за общи рекурсивни функции, установено е че има групи от прости инструкции, които, когато се сложат заедно, са в състояние да произведът всякакви изчисления. Работата на Гьодел показа, че понятието за изчисление е по същество уникално.
|