Машина Тьюринга

@Electroflower · Регистрация: 05.01.2012

Студворк — интернет-сервис помощи студентам

Ребят, Всем привет! Есть профи по тьюрингу?
Задача такова: Нужно проверить на четность количество единиц. Алфавит: (1,0).
Если единиц четное кол-во, то ответ "ДА", если нечетное "НЕТ"
Вот что получилось: (находит только если подряд стоят...)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//---------------------------------------------------------------------------
 
#include <vcl.h>
#pragma hdrstop
 
#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
 
 
int MT (AnsiString s)
{
Form1->ListBox1->Clear();
int b=0,q=0,i=1,q1;
 
          while (b==0)
         {q1=q; switch (q)
 
{
case 0: switch (s[i])
   {case '0': q=0; break; case '1': q=1;break; case ' ': b=1; break;}
   break;
case 1: switch (s[i])
   {case '0': q=0; break; case '1': q=2;break; case ' ': b=1; break;}
   break;
case 2: switch (s[i])
   {case '0': q=0; break; case '1':{q=3;b=1;break;} case ' ': b=1; break;}
   break;
case 3: switch (s[i])
   {case '0': q=0; break; case '1':{q=4;b=1;break;} case ' ': b=1; break;}
   break;
case 4: switch (s[i])
   {case '0': q=0; break; case '1':{q=5;b=1;break;} case ' ': b=1; break;}
   break;
case 5: switch (s[i])
   {case '0': q=0; break; case '1':{q=6;b=1;break;} case ' ': b=1; break;}
   break;
}
           Form1->ListBox1->Items->Add("(q"+IntToStr(q1)+" "+s[i]+"-->q"+IntToStr(q)+" "+s[i]+" R, "+s+")");
           i++;
           }
   return(q);
  }
 
 
void __fastcall TForm1::Button1Click(TObject *Sender)
{
int rez,i=0;
AnsiString s;
while (Form1->StringGrid1->ColCount!=i)
{
s=s+Form1->StringGrid1->Cells[i][0];
i++;
}
s=s+' ';
rez=MT(s);
if (rez%2==0)
Label1->Caption="Да";
else
Label1->Caption="Нет";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button4Click(TObject *Sender)
{
Form1->StringGrid1->ColCount=1;
Form1->StringGrid1->Cells[0][0]=' ';
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{
if (Form1->StringGrid1->ColCount!=1 ||
Form1->StringGrid1->Cells[Form1->StringGrid1->ColCount-1][0]==1 ||
Form1->StringGrid1->Cells[Form1->StringGrid1->ColCount-1][0]==0)
Form1->StringGrid1->ColCount++;
Form1->StringGrid1->Cells[Form1->StringGrid1->ColCount-1][0]=1;
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button3Click(TObject *Sender)
{
if (Form1->StringGrid1->ColCount!=1 ||
Form1->StringGrid1->Cells[Form1->StringGrid1->ColCount-1][0]==1 ||
Form1->StringGrid1->Cells[Form1->StringGrid1->ColCount-1][0]==0)
Form1->StringGrid1->ColCount++;
Form1->StringGrid1->Cells[Form1->StringGrid1->ColCount-1][0]=0;
}
//---------------------------------------------------------------------------

@BRcr · 27.08.2012, 01:10

Не очень понимаю, как это связано с тестом Тьюринга... впрочем, есть достаточно много его вариаций...

Но вот что я знаю точно, так то, что для подсчета количества единичек в текстовой строчке не нужно толпы switch - для этого вполне хватит цикла со счетчиком: если очередной символ является единицей, инкрементируем счетчик. Вот и все, собственно, потом выясняем четность числа в счетчике.

@OhMyGodSoLong · 27.08.2012, 02:41

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

Алфавит: {0, 1} + E для пустой ячейки.
Состояния: {Y, N} + HALT для останова.
На ленте записана последовательность 0 и 1.
Головка машины указывает на самую левую цифру.
Начальное состояние: Y.

Формат правил: текущий символ @ текущее состояние → новый символ @ новое состояние (направление сдвига головки).

Правила:
1 @ Y → 1 @ N (R)
1 @ N → 1 @ Y (R)
0 @ Y → 0 @ Y (R)
0 @ N → 0 @ N (R)
E @ Y → 1 @ HALT
E @ N → 0 @ HALT

После останова в текущей ячейке 1, если число единиц чётное, и 0 в противном случае.

@Electroflower · 28.08.2012, 13:43 **[ТС]**

BRcr, вот вы посоветовали и теперь все работает, теперь не могу разобраться как этот алфавит и правила записывать....
Вот что вышло(вполне просто):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void __fastcall TForm1::Button2Click(TObject *Sender)
{
if (Form1->StringGrid1->ColCount!=1 ||
Form1->StringGrid1->Cells[Form1->StringGrid1->ColCount-1][0]==1 ||
Form1->StringGrid1->Cells[Form1->StringGrid1->ColCount-1][0]==0)
Form1->StringGrid1->ColCount++;
Form1->StringGrid1->Cells[Form1->StringGrid1->ColCount-1][0]=1;        
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
if (Form1->StringGrid1->ColCount!=1 ||
Form1->StringGrid1->Cells[Form1->StringGrid1->ColCount-1][0]==1 ||
Form1->StringGrid1->Cells[Form1->StringGrid1->ColCount-1][0]==0)
Form1->StringGrid1->ColCount++;
Form1->StringGrid1->Cells[Form1->StringGrid1->ColCount-1][0]=0;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button3Click(TObject *Sender)
{ int q=0;
int i,z;
z=StrToInt(Edit1->Text);
for (i=0;i<z;i++)if (Form1->StringGrid1->Cells[i][0]==1){q++;}
if (q%2==0){ShowMessage("DA");}else {ShowMessage("NO");}
 
 
 
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button4Click(TObject *Sender)
{
Form1->StringGrid1->ColCount=1;
Form1->StringGrid1->Cells[0][0]=' ';        
}
//---------------------------------------------------------------------------

Добавлено через 1 минуту
~OhMyGodSoLong~, и вам спасбо^^

@BRcr · 28.08.2012, 17:12

Сообщение от ~OhMyGodSoLong~

После останова в текущей ячейке 1, если число единиц чётное, и 0 в противном случае.

~OhMyGodSoLong~, это как-то не уверен я, что правильно понял.

Что будет вот в этих случаях по правилам преобразований состояния и направлений?
1 @ Y → 0 @ ? (?)
0 @ Y → 1 @ ? (?)
1 @ N → 0 @ ? (?)
0 @ N → 1 @ ? (?)

Добавлено через 1 минуту
Electroflower, все не так уж и сложно, правда?

@Electroflower · 29.08.2012, 10:20 **[ТС]**

BRcr, да, не так все сложно, но вот с алфавитом плохо дело....
1 @ Y → 1 @ N (R)
1 @ N → 1 @ Y (R)
0 @ Y → 0 @ Y (R)
0 @ N → 0 @ N (R)
E @ Y → 1 @ HALT
E @ N → 0 @ HALT

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита табличной части. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@BRcr 4043 / 2333 / 292 Регистрация: 03.02.2011 Сообщений: 5,066 Записей в блоге: 10
	27.08.2012, 01:10
	Не очень понимаю, как это связано с тестом Тьюринга... впрочем, есть достаточно много его вариаций... Но вот что я знаю точно, так то, что для подсчета количества единичек в текстовой строчке не нужно толпы switch - для этого вполне хватит цикла со счетчиком: если очередной символ является единицей, инкрементируем счетчик. Вот и все, собственно, потом выясняем четность числа в счетчике. 0

@OhMyGodSoLong ~ Эврика! ~ 1258 / 1007 / 74 Регистрация: 24.07.2012 Сообщений: 2,002
	27.08.2012, 02:41
	Не знаю, что там у вас в коде, но для машины Тьюринга программа такая. Алфавит: {0, 1} + E для пустой ячейки. Состояния: {Y, N} + HALT для останова. На ленте записана последовательность 0 и 1. Головка машины указывает на самую левую цифру. Начальное состояние: Y. Формат правил: текущий символ @ текущее состояние → новый символ @ новое состояние (направление сдвига головки). Правила: 1 @ Y → 1 @ N (R) 1 @ N → 1 @ Y (R) 0 @ Y → 0 @ Y (R) 0 @ N → 0 @ N (R) E @ Y → 1 @ HALT E @ N → 0 @ HALT После останова в текущей ячейке 1, если число единиц чётное, и 0 в противном случае. 0

@Electroflower Shiningemerald 384 / 117 / 22 Регистрация: 05.01.2012 Сообщений: 951
	29.08.2012, 10:20 [ТС]
	BRcr, да, не так все сложно, но вот с алфавитом плохо дело.... 1 @ Y → 1 @ N (R) 1 @ N → 1 @ Y (R) 0 @ Y → 0 @ Y (R) 0 @ N → 0 @ N (R) E @ Y → 1 @ HALT E @ N → 0 @ HALT 0